首页 > 代码库 > 3622 假期

3622 假期

2024-08-16 19:51:17   217人阅读

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

 

3622 假期


联系
我们