題目描述

約翰家的 N 頭奶牛正在排隊游行抗議。一些奶牛情緒激動，約翰測算下來，排在第 i 位的奶牛 的理智度為 A i ，數(shù)字可正可負。 約翰希望奶牛在抗議時保持理性，為此，他打算將這條隊伍分割成幾個小組，每個抗議小組的理 智度之和必須大于或等于零。奶牛的隊伍已經(jīng)固定了前后順序，所以不能交換它們的位置，所以分在 一個小組里的奶牛必須是連續(xù)位置的。除此之外，分組多少組，每組分多少奶牛，都沒有限制。 約翰想知道有多少種分組的方案，由于答案可能很大，只要輸出答案除以 1000000009 的余數(shù)即 可。

輸入

? 第一行：單個整數(shù) N，1 ≤ N ≤ 100000 ? 第二行到第 N + 1 行：第 i + 1 行有一個整數(shù) A i ，?10?5?≤ A i ≤ 10?5

輸出

? 單個整數(shù)：表示分組方案數(shù)模 1000000009 的余數(shù)

?

樣例輸入

4 2 3 -3 1

樣例輸出

4

提示

如果分兩組，可以把前三頭分在一組，或把
后三頭分在一組；如果分三組，可以把中間兩頭
分在一組，第一和最后一頭奶牛自成一組；最后
一種分法是把四頭奶牛分在同一組里。 題解： 樸素做法 if(sum[i]-sum[j]>=0)f[i]+=f[j]. 于是發(fā)現(xiàn)只要sum[j]<=sum[i] 即可轉(zhuǎn)移 然后以sum[i]為下標,維護樹狀數(shù)組即可,沒事可以離散化一下. 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int mod=1000000009,N=100005; 8 int gi(){ 9 int str=0,f=1;char ch=getchar(); 10 while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar(); 12 return str*f; 13 } 14 int a[N],id[N],n;ll Tree[N*4],sum[N],b[N],f[N]; 15 int pf(ll x) 16 { 17 int l=1,r=n,mid; 18 while(l<=r) 19 { 20 mid=(l+r)>>1; 21 if(b[mid]==x)return mid; 22 if(x>b[mid])l=mid+1; 23 else r=mid-1; 24 } 25 return 0; 26 } 27 void add(int sta,ll x){for(int i=sta;i<=n;i+=(i&(-i)))Tree[i]+=x,Tree[i]%=mod;} 28 ll getsum(int sta) 29 { 30 ll sum=0; 31 for(int i=sta;i>=1;i-=(i&(-i)))sum+=Tree[i],sum%=mod; 32 return sum; 33 } 34 int main() 35 { 36 n=gi(); 37 for(int i=1;i<=n;i++)a[i]=gi(),sum[i]=sum[i-1]+a[i],b[i]=sum[i]; 38 sort(b+1,b+n+1); 39 for(int i=1;i<=n;i++) 40 { 41 id[i]=pf(sum[i]); 42 } 43 for(int i=1;i<=n;i++) 44 { 45 f[i]=getsum(id[i]); 46 if(sum[i]>=0)f[i]++; 47 f[i]%=mod; 48 add(id[i],f[i]); 49 } 50 printf("%lld",f[n]%mod); 51 return 0; 52 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yuzao/p/7053785.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【USACO】奶牛抗议 树状数组+dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。