假期 题解

假期 题解

假期

题目

经过几个月辛勤的工作，FJ决定让奶牛放假。假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。

输入

第一行：N,P,Q.
第二行：N个数字，中间用一个空格隔开,每个数都在longint范围内。

输出

一个整数，奶牛们能获得的最大享受指数。

样例

input
5 2 4
-9 -4 -3 8 -6

output
5

解题思路

前缀和
假如右端点是固定的
左端点越小最后的值越大
所以单调队列维护递增（维护左端点）

代码

#include
#include
#include
using namespace std;
long long n,x,y,h=1,t,ans=-2147483647,a[100020],q[100020],s[100020];  //记得开long long
int main()
{scanf("%lld%lld",&n,&x);for (int i=1;i<=n;i++){scanf("%lld",&a[i]);s[i]=s[i-1]+a[i];  //前缀和}for (int r=1;r<=n;r++){while (h<=t&&s[q[t]-1]>=s[r-1]) t--;  //找更小的左端点，包含的数少却更大，对后面的答案没有贡献q[++t]=r;  //保存进队列while (h<=t&&r-x>q[h]-1) h++;  //超出范围if (ans<s[r]-s[q[h]-1])  //更新答案ans=s[r]-s[q[h]-1]; }cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！