奶牛抗议洛谷p2344

题目背景

Generic Cow Protests, 2011 Feb

题目描述

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。

约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。

约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 100000

• 第二行到第N + 1 行：第i + 1 行有一个整数Ai，−10^5 ≤ Ai ≤ 10^5

输出格式：

单个整数：表示分组方案数模1000000009 的余数

输入输出样例

输入样例#1： 4 2 3 -3 1 输出样例#1： 4

说明

解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

• 记录前缀理智和 si 。 l,l+1,l+2,…,r-1,r 能够分成一组， iff s[r]>=s[l-1] • 令 dp [ i ] 表示以 i 作为某一段的结尾的分组方式。 dp [n] 就是要求的答案 • dp [ i ]= ∑ dp [j] ……j< i 且 s[j]<=s[ i ] <=s[ i ] 的 dp [j] 的和可以使用树状数组维护

#include<iostream> #include<cstdio> #include<algorithm> #define f(i,l,r) for(i=(l);i<=(r);i++) using namespace std; const int MAXN=100005,MOD=1000000009; struct Node{ int v,id,Hash; bool operator < (const Node& x)const{ return v<x.v; } }sum[MAXN]; int n,a[MAXN],Tree[MAXN],Hash[MAXN],sz; bool cmp(Node a,Node b) { return a.id<b.id; } void Add(int x,int d) { while(x<=sz){ Tree[x]=(Tree[x]+d)%MOD; x+=x&(-x); } } int Query(int x) { int res=0; while(x>0){ res=(res+Tree[x])%MOD; x-=x&(-x); } return res; } int main() { int i,j=1,tot=0,pos,ans; scanf("%d",&n); sum[0].v=sum[0].id=0; f(i,1,n){ scanf("%d",&a[i]); sum[i].v=sum[i-1].v+a[i]; sum[i].id=i; } sort(sum,sum+1+n); sum[0].Hash=1; f(i,1,n){ if(sum[i].v!=sum[i-1].v){ sum[i].Hash=++j; } else sum[i].Hash=j; } sz=j; sort(sum,sum+1+n,cmp); Add(sum[0].Hash,1); f(i,1,n){ ans=Query(sum[i].Hash); Add(sum[i].Hash,ans); } printf("%d\n",ans); return 0; }