P1569 [USACO11FEB]属牛的抗议Generic Cow Prote…
题目描述
约翰家的N头奶牛聚集在一起，排成一列，正在进行一项抗议活动。第i头奶牛的理智度 为Ai，Ai可能是负数。约翰希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成 若干个小组，每个小组内的奶牛的理智度总和都要大于等于零。由于奶牛是按直线排列的，所以 一个小组内的奶牛位置必须是连续的。 请帮助约翰计算一下，最多分成几组。
输入输出格式
输入格式：
第1行包含1个数N，代表奶牛的数目。
第2至N+1行每行1个整数Ai。
输出格式：
输出文件有且仅有一行，包含1个正整数即为最多组数。
若无法满足分组条件，则输出Impossible。
输入输出样例
输入样例#1：
4
2
3
-3
1
输出样例#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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm> 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;
}