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

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

题目描述

Farmer John's N (1 <= N <= 100,000) cows are lined up in a row and numbered 1..N. The cows are conducting another one of their strange protests, so each cow i is holding up a sign with an integer A_i (-10,000 <= A_i <= 10,000).

FJ knows the mob of cows will behave if they are properly grouped and thus would like to arrange the cows into one or more contiguous groups so that every cow is in exactly one group and that every group has a nonnegative sum.

Help him count the number of ways he can do this, modulo 1,000,000,009.

By way of example, if N = 4 and the cows' signs are 2, 3, -3, and 1, then the following are the only four valid ways of arranging the cows:

(2 3 -3 1) 
(2 3 -3) (1) 
(2) (3 -3 1) 
(2) (3 -3) (1) 
Note that this example demonstrates the rule for counting different orders of the arrangements. 

约翰家的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。

洛谷题解

题目有坑，说的是大于0分一组，其实等于0也可以分一组

记录前i个奶牛的智商的和为sum[i]

容易证明，只有sum[i]>=0的时候，前i个奶牛才可以分组

那么就可以得到状转方程：

f(i)=max{f(k)+1} (1<=k<i, f(k)>0 && sum[i]-sum[j]>=0)

初始化dp数组的时候，sum[i]>=0的话dp[i]=1（至少分成一组），否则dp[i]=0（不可以分组）

来一发C++的代码

线性

区间dp

#include <iostream>
#include <string>
#define maxn 1005
using namespace std;
int n;
int a[maxn];
int dp[maxn];
int sum[maxn]; //sum[i]即1~i的序列和
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        if(sum[i]>=0) dp[i]=1; //至少可以分成1组
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<i;++j)
            if(dp[j]>0 && sum[i]-sum[j]>=0) dp[i]=max(dp[i],dp[j]+1);
    if(!dp[n]) cout<<"Impossible"<<endl;
    else cout<<dp[n]<<endl;
    return 0;
}