题目描述
给定一行 \(n\) 个非负整数 \(a[1]..a[n]\) 。现在你可以选择其中若干个数，但不能有超过 \(k\) 个连续的数字被选择。你的任务是使得选出的数字的和最大。
输入格式
第一行两个整数 \(n\) ，\(k\)
以下n行，每行一个整数表示 \(a[i]\)。
输出格式
输出一个值表示答案。
输入输出样例
输入 #1
5 2
1
2
3
4
5
输出 #1
12
说明/提示
对于20%的数据，n <= 10
对于另外20%的数据， k = 1
对于60%的数据，n <= 1000
对于100%的数据，1 <= n <= 100000，1 <= k <= n，0 <= 数字大小 <= 1,000,000,000
时间限制500ms
没错，我又来水题啦。
首先，我们会想到 O(\(n^2\) ) 的dp
设 \(f[i]\) 表示从前 \(i\) 个数的最大价值。
那么就会有转移
\(f[i] = max(f[i], f[i-k-1] + sum[i] - sum[i-k+1-1])\) (后面我拆开写主要是为了好理解，实际上化简一下就可以)。
\(k\) 是我们枚举的要选的连续的数的个数，即区间长度。
这样肯定会 TLE 得啦。
但有没有觉得这个柿子很熟悉，这不就是求 \(i-k-1 , i\) 的最大值。
直接上单调队列优化，记得一开始要把前 \(k\) 个点先入队，在去更新其他的。
我们更新 \(i\) 的时候，要先把 \(i\) 入队在更新，因为他可以取到 \(i\) 也就相当于不选这个数。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
int n,k,x,head,tail;
int sum[100010],f[100010],q[100010];
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
signed main()
{
n = read(); k = read();
for(int i = 1; i <= n; i++)
{
x = read();
sum[i] = sum[i-1] + x;//维护一个前缀和
}
head = 1, tail = 0;
q[++tail] = 0;
for(int i = 1; i <= k; i++)//先把前k的点入队
{
f[i] = sum[i];
while(head <= tail && f[q[tail] - 1] - sum[q[tail]] <= f[i-1] - sum[i]) tail--;
q[++tail] = i;
}
for(int i = k+1; i <= n; i++)
{
while(head <= tail && q[head] < i - k) head++;//把过期的扔掉
while(head <= tail && f[q[tail]-1] - sum[q[tail]] <= f[i-1] - sum[i]) tail--;//把不优的情况也扔掉
q[++tail] = i; //先入队在更新
f[i] = f[q[head]-1] + sum[i] - sum[q[head]];
}
printf("%lld\n",f[n]);
return 0;
}
另外还有一道双倍经验的题 P2627 [USACO11OPEN]Mowing the Lawn G。
这个题和上面那道题差不多，只不过有个小细节是要让节点先更新在入队（至于为什么自己可以想想）。