C/C++教程

CCF 202109-2 非零段划分(动态规划法,过了70%)

本文主要是介绍CCF 202109-2 非零段划分(动态规划法,过了70%),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<stdio.h>
int A[10001];/*使用动态规划法,开辟数组空间存放每处理完一个B后各种数p划分下的非零段个数,根据题意,p不超过10000*/
int flag[10001];/*flag用于记录非零段是否连续,全局变量初始时默认为零,所以省去了赋初值的步骤*/
int main(){
	int n;
	scanf("%d",&n);
	int B,num=0,p=0,now=0;/*now记录当前遇到的被处理数B的最大值*/
	for(int i=0;i<n;i++){
		scanf("%d",&B);
		if(B>now){
			now=B;
		}
		while(p<=now){/*p记录当前划分使用的数*/ 
			if(B>=p&&p!=0){/*如果被处理数B>=p*/
				if(flag[p]==0){/*且flag为零,即不连续,记录非零段个数的A[p]就要加一*/ 
					A[p]++;
				}
				flag[p]=1;
			}else{
				flag[p]=0;
			}
			p++;
		}
		p=0;
	}
	for(int i=0;i<=now;i++){
		if(A[num]<A[i]){/*找到所有可能划分数的非零段个数的最大值*/
			num=i;
		} 
	}
	printf("%d",A[num]);
	return 0;
}

题目描述

A1,A2,⋯,An 是一个由 n 个自然数(非负整数)组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段,当且仅当以下条件同时满足:

  • 1≤i≤j≤n;
  • 对于任意的整数 k,若 i≤k≤j,则 Ak>0;
  • i=1 或 Ai−1=0;
  • j=n 或 Aj+1=0。

下面展示了几个简单的例子:

  • A=[3,1,2,0,0,2,0,4,5,0,2] 中的 4 个非零段依次为 [3,1,2]、[2]、[4,5] 和 [2];
  • A=[2,3,1,4,5] 仅有 1 个非零段;
  • A=[0,0,0] 则不含非零段(即非零段个数为 0)。

现在我们可以对数组 A 进行如下操作:任选一个正整数 p,然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p,使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值,可取 p=1,即不对 A 做任何修改。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n。

输入的第二行包含 n 个用空格分隔的自然数 A1,A2,⋯,An。

输出格式

输出到标准输出。

仅输出一个整数,表示对数组 A 进行操作后,其非零段个数能达到的最大值。

样例1输入

11
3 1 2 0 0 2 0 4 5 0 2

Data

样例1输出

5

Data

样例1解释

p=2 时,A=[3,0,2,0,0,2,0,4,5,0,2],5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2];此时非零段个数达到最大。

样例2输入

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

Data

样例2输出

4

Data

样例2解释

p=12 时,A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15],4 个非零段依次为 [20]、[15]、[20] 和 [15];此时非零段个数达到最大。

样例3输入

3
1 0 0

Data

样例3输出

1

Data

样例3解释

p=1 时,A=[1,0,0],此时仅有 1 个非零段 [1],非零段个数达到最大。

样例4输入

3
0 0 0

Data

样例4输出

0

Data

样例4解释

无论 p 取何值,A 都不含有非零段,故非零段个数至多为 0。

子任务

70% 的测试数据满足 n≤1000;

全部的测试数据满足 n≤5×105,且数组 A 中的每一个数均不超过 104。

这篇关于CCF 202109-2 非零段划分(动态规划法,过了70%)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!