题目背景
Generic Cow Protests, 2011 Feb
题目描述
约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。
约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。
约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。
首先来看直接DP是肯定过不了的
但是我们要先退出转移方程，然后进行优化
dp[i]代表的是结尾为i的地方的方案数
转移的话就是往前枚举，直到和大于等于0
再之前之前的所有满足数量加上来
这就正好可以用树状数组来维护
我们又发现，是否大于0，只和两个数的大小有关，和具体的值无关，所以我们可以离散化
接下来动态维护就可以了
下面给出代码：（没有离散化，需要的自己写）
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define mod 1000000009 using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int c[10000006]; int n; int a[1000006]; int lowbit(int x){ return x&(-x); } void add(int i,int y){ for(;i<=10000000;i+=lowbit(i)) c[i]=(c[i]+y)%mod; } int solve(int i){ int sum=0; for(;i>=1;i-=lowbit(i)) sum=(sum+c[i])%mod; return sum%mod; } int f[100006]; int sum[100006],s[100006]; int main(){ freopen("01.in","r",stdin); n=rd(); for(int i=1;i<=n;i++){ a[i]=rd(); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) sum[i]+=1000000; for(int i=1;i<=n;i++){ if(sum[i]>=0) f[i]=1; f[i]=(f[i]+solve(sum[i]))%mod; add(sum[i],f[i]%mod); } write(f[n]%mod); return 0; }