经过几个月辛勤的工作，FJ决定让奶牛放假。假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。
第一行：N,P,Q.
第二行：N个数字，中间用一个空格隔开。
一个整数，奶牛们能获得的最大享受指数。
5 2 4
-9 -4 -3 8 -6
5
50% 1≤N≤10000
100% 1≤N≤100000
１<=p<=q<=n
指数在longint范围之内。
提示：
选择第3-4天，享受指数为-3+8=5。
AC代码：
#include<cstdio> #define ll long long using namespace std; const int N=1e5+10; int n,sd,ed,q[N<<1]; ll tmp,ans=-0x7fffffff; ll sum[N]; int main(){ scanf("%d%d%d",&n,&sd,&ed); for(int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]+=sum[i-1]; int h=1,t=0; for(int i=sd;i<=n;i++){ while(sum[q[t]]>=sum[i-sd]&&h<=t) t--; q[++t]=i-sd; while(q[h]<i-ed&&h<=t) h++; tmp=sum[i]-sum[q[h]]; if(ans<tmp) ans=tmp; } printf("%lld",ans); return 0; }
原文：http://www.cnblogs.com/shenben/p/5965970.html