最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个长度为 $n$ 的数组 $w$，其中 $w_i$ 是第 $i$ 个元素的 贡献

我们可以选择的 数组 中的一些 元素，这些元素的 贡献总和 表示我们该种 方案 的 价值

但是，如果方案中出现选择了 连续相邻 且超过 $m$ 个元素，则这些 连续相邻 的元素 贡献 归零

求解一种 方案，使得选择的 元素贡献总和 最大

分析

考虑用 动态规划 来求解本问题

由于 连续选择 超过 $m$ 个元素时，这些元素的 贡献 为 $0$ （相当于没选）

而本题，所有的元素值都是 正整数，故我们的方案中，连续选择的元素数量 一定是 不超过 $m$ 的

• 可以用 反证法 证明，如果方案中有超过 $m$ 个连续元素，则我们不选中间的一个，使他断开，必然不会使方案变差

于是，我们就可以通过 最后一次没有选择的元素，对 集合进行划分

闫氏DP分析法

状态表示-集合 $f_i$：以 $i$ 为右端点的 前缀数组 的选择方案

状态表示-属性 $f_i$：方案的 价值 最大 $Max$

状态计算：

$$ f_i = \max\big\{{ f_{j - 1} + s_i - s_j }\big\} \qquad 0\le i - j \le m $$

跟上一题一样，首先我们把 常量 提出来：$ f_i = s_i + \max\big\{{ f_{j - 1} - s_j }\big\} \qquad 0\le i - j \le m $

由于 $j$ 是有范围的：$i - m \le j \le i$，于是问题就转化为 滑动窗口求极值 的问题了

我们用一个记录 $f_{j-1} - s_j$ 的 单调递减 的 队列 在 队头 维护一个 最大值 即可

Code

时间复杂度： $O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N], f[N];
int que[N];

LL g(int i)
{
    return f[max(0, i - 1)] - s[i];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]), s[i] += s[i - 1];

    int hh = 0, tt = 0; que[0] = 0;   //  0 <= i - j <= m
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && g(i) >= g(que[tt])) tt -- ;
        que[ ++ tt] = i;  // i - j >= 0 故先入队
        while (hh <= tt && i - que[hh] > m) hh ++ ;
        f[i] = s[i] + g(que[hh]);
    }
    printf("%lld\n", f[n]);
    return 0;
}