3622 假期

?

?時間限制: 1 s ?空間限制: 64000 KB ?題目等級 : 黃金 Gold 題解 題目描述?Description

經過幾個月辛勤的工作，FJ決定讓奶牛放假。假期可以在1…N天內任意選擇一段（需要連續），每一天都有一個享受指數W。但是奶牛的要求非常苛刻，假期不能短于P天，否則奶牛不能得到足夠的休息；假期也不能超過Q天，否則奶牛會玩的膩煩。FJ想知道奶牛們能獲得的最大享受指數。

?

輸入描述?Input Description

第一行：N,P,Q.

第二行：N個數字，中間用一個空格隔開。

輸出描述?Output Description

一個整數，奶牛們能獲得的最大享受指數。

樣例輸入?Sample Input

5 2 4?

-9 -4 -3 8 -6?

樣例輸出?Sample Output

5

數據范圍及提示?Data Size & Hint

50% 1≤N≤10000

100% 1≤N≤100000

１<=p<=q<=n

指數在longint范圍之內。

提示：

選擇第3-4天，享受指數為-3+8=5。

分類標簽?Tags?點此展開?

暫無標簽 題解： 動態規劃，先求一個前綴和sum，ans=max(ans,sum[i]-sum[k])(i-p<=k<=i-q)?
根據上式，若ans最大，則sum[k]盡量小，所以單調隊列維護區間i-q~i-p的最小值即可。

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; }

?

轉載于:https://www.cnblogs.com/shenben/p/5965970.html

總結

以上是生活随笔為你收集整理的3622 假期的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。