一道简单的动态规划优化题。

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1077f2/

题意

给你一个数列 $a$，你需要选择 $m$ 个元素，使得连续的 $k$ 个元素都至少有一个被选中。

需要你最大化选出来的所有数的和。

解法

容易想到动态规划，定义 $f(i,j)$ 为前 $i$ 个元素选了 $j$ 个，且最后一个为 $i$ 时的最大和。
连续 $k$ 个必须选一个，即限定转移范围为 $[i – k,i – 1]$，那么有转移方程：

$$f(i,j) = \max \limits _{i – k \le p \le i – 1}f(p,j – 1) + a_i$$
朴素转移是 $O(n^3)$ 的，但看到连续区间取最大值，可以想到用单调队列优化。
具体地，维护关于 $f(p,j – 1)$ 的 $[i – k,i – 1]$ 区间的最大值单调队列。最外层枚举选了的元素个数 $j$ 进行更新。
最终复杂度 $O(n^2)$.

空间上可以使用滚动数组稍微优化。
判断无解的话，最后选的一个元素一定在 $[n – k + 1,n]$ 的区间内，设置初值为负无穷大，而 $f(0,0) = 0$ 进行合法转移即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
inline char nc() { static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; }
template<typename T> 
inline T read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 5e3 + 100;
#define int long long
int n,k,x,a[maxn];
int cost[2][maxn],f[2][maxn],q[maxn],qt,qh;
signed main()
{
    read(n), read(k), read(x);
    for (int i = 1; i <= n; ++i) read(a[i]);
    int now = 0, last = 1;
    memset(f[last], ~0x3f, sizeof(f[last]));
    f[last][0] = 0;
    for (int j = 1; j <= x; ++j)  //choose j
    {
        qh = qt = 1, q[1] = 0;
        for (int i = 1; i <= n; ++i)
        {
            while (qt >= qh && i - q[qh] > k) ++qh;
            f[now][i] = f[last][q[qh]] + a[i];
            while (qt >= qh && f[last][q[qt]] <= f[last][i]) --qt;
            q[++qt] = i;
        }
        now ^= 1, last ^= 1;
    }
    int ans = -(1ll << 60);
    for (int i = n - k + 1; i <= n; ++i) ans = max(ans, f[last][i]);
    if (ans >= 0) printf("%lld\n", ans);
    else puts("-1");
    return 0;
}