P1569 [USACO11FEB]属牛的抗议Generic Cow Prote…

题目描述

约翰家的N头奶牛聚集在一起，排成一列，正在进行一项抗议活动。第i头奶牛的理智度 为Ai，Ai可能是负数。约翰希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成 若干个小组，每个小组内的奶牛的理智度总和都要大于等于零。由于奶牛是按直线排列的，所以 一个小组内的奶牛位置必须是连续的。 请帮助约翰计算一下，最多分成几组。

输入输出格式

输入格式：

第1行包含1个数N，代表奶牛的数目。

第2至N+1行每行1个整数Ai。

输出格式：

输出文件有且仅有一行，包含1个正整数即为最多组数。

若无法满足分组条件，则输出Impossible。

输入输出样例

输入样例#1：

423-31

输出样例#1：

3

说明

【数据规模和约定】

30%的数据满足N≤20。

100%的数据满足N≤1000，|Ai|≤100000。

这道题错了老久跟管理员反映终于改了。。。

为什么说这是一个炒鸡弱化版。因为原本需要用dp + 树状数组。

结果现在。。

我都没好意思挂上USACO的标签

f[i]表示第i个及其之前的最大分组数。

然后有两个细节需要注意一下：

1、有可能整个区间囫囵分成一组；

2、当这个区间不能分组时会被记做0，而当后面的区间需要用到这个区间的时候就会出错（即f[j] = 0的时候，可能本来f[i]应该也是0，但是由于这个的缘故导致f[i]成了1，因此需要特判f[j]是否能够被分组，即f[j] ！= 0）、

最紧总是注意不到这些细节。。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         const int MAXN = 100000 + 10;int n;int s[MAXN];int f[MAXN];int main(){	scanf("%d", &n);	for(int i =1;i <= n;i ++)	{		int temp;		scanf("%d", &temp);		s[i] = s[i - 1] + temp;	}	for(int i = 1;i <= n;i ++)	{		if(s[i] >= 0)f[i] = 1;		for(int j = 1;j < i;j ++)		{			if(s[i] - s[j] >= 0 && f[j] != 0)			{				f[i] = std::max(f[i],f[j] + 1);			}		}	}	if(s[n]<=0)	{		printf("Impossible");		return 0;	}	printf("%d", f[n]);	return 0;}