JZYZOJ 1360 [usaco2011feb]人品问题 DP 树状数组 离散化

http://172.20.6.3/Problem_Show.asp?id=1360

好想好写

代码

1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>  
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=100010;
 9 const long long modn=1000000009;
10 long long n,siz;
11 long long a[maxn]={},b[maxn]={};
12 long long t[maxn]={};
13 long long lowbit(long long x){return x&-x;}
14 long long sum(long long x){
15     long long tsn=0;
16     while(x){
17         tsn+=t[x];tsn%=modn;
18         x-=lowbit(x);
19     }return tsn;
20 }
21 void add(long long x,long long v){
22     while(x<=siz){
23         t[x]+=v;t[x]%=modn;
24         x+=lowbit(x);
25     }
26 }
27 int main(){
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++){
30         scanf("%I64d",&a[i]);
31         a[i]+=a[i-1];b[i]=a[i];
32     }b[n+1]=0;
33     sort(b+1,b+2+n);
34     siz=unique(b+1,b+2+n)-b-1;
35     for(int i=1;i<=n;i++){
36         a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
37     }long long zer=lower_bound(b+1,b+1+siz,0)-b;
38     add(zer,1);
39     long long x;
40     for(int i=1;i<=n;i++){
41         x=sum(a[i]);
42         if(i==n){
43             printf("%I64d\n",x);
44             break;
45         }
46         add(a[i],x);
47     }
48     return 0;
49 }