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

题目描述

给定一个长度为 $n$ 的数组 $w$，以及一个正整数 $m$

其中 $w_i$ 表示第 $i$ 个 元素 的 价值

求一种选择元素的 方案：

1. 使得选择的 相邻元素 之间相差 不超过 $m-1$ 个 不选 的元素
2. 选择的元素总贡献 最小

分析

求 一维数组选择方案，不妨用 动态规划 将问题拆分成一个个 子问题 来求解，最后 合并

状态表示-集合 $f_i$：以 $i$ 为 右端点 的 前缀区间，选择 第 $i$ 个元素的 方案

状态表示-属性 $f_i$：方案选的元素 总贡献最小 $Min$

状态计算 ：

$$\begin{aligned} &f_i = \min\{{ f_j + w_i }\} & (0 \le i - j - 1 \le m-1) \\\\ ~ \\\\ \Rightarrow \quad &f_i = w_i + \min\{{f_j}\} & (1 \le i - j \le m) \end{aligned}$$

有限范围 的 $j$ 和分离开常量后的 最小值函数，直接套 单调队列模板 即可

然后是关于如何 统计答案

y 总演示的是在最后，暴力枚举 最终状态 f[i]，其中 $n - m + 1 \le i \le n$ （y总常数有点大）

这里可以巧妙利用我们的 滑动窗口

首先我们知道，单调队列 维护的是 $i - m \le j \le i - 1$ 的区间的 $f_j$ 状态最小值

循环迭代完第 $n$ 轮后，$j$ 的范围为 $n - m \le j \le n$

$f[n]$ 进入滑动窗口，但是我们的代码中，判断滑动窗口的大小要在 $n+1$ 轮里进行

所以结束的时候，把滑动窗口往后多划一位，把 $j$ 的范围定在 $n - m + 1 \le j \le n$

则 单调队列 的 队头元素，就是该范围内的 值最小的最终状态，输出 队头元素 即可

Code

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

初始状态： $f_0$

目标状态： $f_j \quad (n - m + 1 \le j \le n)$

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

using namespace std;

const int N = 2e5 + 10;

int n, m;
int w[N], f[N];
int que[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && i - que[hh] > m) hh ++ ;
        f[i] = f[que[hh]] + w[i];
        while (hh <= tt && f[que[tt]] >= f[i]) tt -- ;
        que[ ++ tt] = i;
    }

    if (n + 1 - m > que[hh]) hh ++ ;   //滑动窗口往后滑动一位

    printf("%d\n", f[que[hh]]);

    return 0;
}