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。

輸入輸出樣例

4
2
3
-3
1

3

說明

【數據規模和約定】

30%的數據滿足N≤20。

100%的數據滿足N≤1000，|Ai|≤100000。

一開始想到用首碼和維護了，但是，還是不自信啊，，

題解裡面用到了一個很巧妙的東西就是

if(dp[j]>0&&sum[i]-sum[j]>=0)

就說明他們兩個可以不在一個分組裡面

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001];
19 int sum[10001];
20 int main()
21 {
22     int i,j,k;
23     read(n);
24     for(int i=1;i<=n;i++)
25     {
26         read(a[i]);
27         sum[i]=sum[i-1]+a[i];
28         if(sum[i]>=0)
29             dp[i]=1;
30     }    
31        for(int i=1;i<=n;i++)
32            for(int j=1;j<i;j++)
33                if(dp[j]>0&&sum[i]-sum[j]>=0)
34                dp[i]=max(dp[i],dp[j]+1);
35     dp[n]==0?printf("Impossible"):printf("%d",dp[n]);    
36     return 0;
37 }