题目描述
今天是小Z的生日,同学们为他带来了一块蛋糕。
这块蛋糕是一个长方体,被用不同色彩分成了N个相同的小块,每小块都有对应的幸运值。
小Z作为寿星,自然希望吃到的第一块蛋糕的幸运值总和最大,但小Z最多又只能吃M小块(M≤N)的蛋糕。
吃东西自然就不想思考了,于是小Z把这个任务扔给了学OI的你,请你帮他从这N小块中找出连续的k块蛋糕(k≤M),使得其上的幸运值最大。
输入格式
第一行包含两个整数N和M,表示共有N小块蛋糕,小Z最多只能吃M小块。
第二行包含空格隔开的N个整数,第i个整数Pi代表第 i 小块蛋糕的幸运值。
输出格式
输出包含一个整数,为小Z能够得到的最大幸运值。
数据范围
1≤N≤500000,
−500≤Pi≤500
输入样例:
5 2
1 2 3 4 5
输出样例:
9
(单调队列) $O(n)$
时间复杂度分析:O(n)
C++ 代码
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
int a[500010];
int q[500010];
int n,m;
int DPMax(int n,int m){
int res = INT_MIN;
int head = 0,tail = 0;
for(int i=0;i<=n;i++){
while(head<=tail && q[head]<i-m) head++;
res=max(res,a[i]-a[q[head]]);
while(head<=tail && a[i]<=a[q[tail]]) tail--;
q[++tail] = i;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
a[i] +=a[i-1];
}
memset(q,0,sizeof(q));
printf("%d",DPMax(n,m));
return 0;
}
大佬,请问为什么这里的tail是从0开始呢?如果从-1开始就会错....
orz膜拜奆佬
大佬tql