方法一：状态机+单调队列优化 $DP$

本题在 $n$ 个烽火台中选择若干个可以看作走 $n$ 步，每步都在 点燃/不点燃 之间进行选择（要保证连续不点燃的长度 < $m$），最后选出最小的代价。

状态表示：
f[i][0] 表示在前 $i$ 个烽火台中不点燃第 $i$ 个烽火台的所有方案中的最小代价；
f[i][1] 表示在前 $i$ 个烽火台中点燃第 $i$ 个烽火台的所有方案中的最小代价。

在确定了第 $i$ 个烽火台的状态下，可以枚举最后这个烽火台前面连续不点燃的烽火台长度。

• 点燃第 $i$ 个烽火台
  $i$ 前面最多连续不点燃 $m-1$ 个烽火台。假设 $i$ 前面最多不点燃连续的 $k$（$0 \le k < m$） 个烽火台，那么对于烽火台 $i-k$ 一定要被点燃，否则就会破坏 $i$ 前面最多不点燃连续的 $k$ 个烽火台这个条件。此时点燃烽火台的代价为 f[i-k][1]+w[i]。
  由于当 $k$ 不同时，得到的代价也不同，所以要维护 $i$ 前面长度为 $m$ 的区间的 f[k][1] 的最小值。
• 不点燃第 $i$ 个烽火台
  $i$ 前面最多连续不点燃 $m-2$ 个烽火台。同理可得要维护 $i$ 前面长度为 $m-1$ 的区间的 f[k][1] 的最小值。

状态转移：

f[i][0] = min(f[k][1])，其中 $i-m<k<i$。

f[i][0] = min(f[k][1]) + w[i]，其中 $i-m \le k<i$。

代码实现

根据上面的分析 f[i][0] 的计算可通过维护一个长度为 $m-1$ 的单调队列，f[i][1] 的计算可通过维护一个长度为 $m$ 的单调队列来实现计算。

最终输出 min(f[n][0], f[n][1]) 即可。

代码模板如下：

#include <iostream>

using namespace std;

const int N = 200010;
int a[N];
int n, m;
int f[N][2];
int q0[N], q1[N];

int main() {
    cin >> n >> m;

    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    int h0 = 0, t0 = -1, h1 = 0, t1 = -1;
    q0[++ t0] = q1[++ t1] = 0;

    for(int i = 1; i <= n; i ++) {
        if(i - q0[h0] >= m) h0 ++;
        if(i - q1[h1] > m) h1 ++;

        f[i][0] = f[q0[h0]][1];
        f[i][1] = f[q1[h1]][1] + a[i];

        while(h0 <= t0 && f[q0[t0]][1] > f[i][1]) t0 --;
        q0[++ t0] = i;

        while(h1 <= t1 && f[q1[t1]][1] > f[i][1]) t1 --;
        q1[++ t1] = i;
    }

    cout << min(f[n][0], f[n][1]) << endl;

    return 0;
}

时间复杂度为 $O(n)$。

方法二：线性+单调队列优化 $DP$

方法一中不论是对 f[i][1] 还是对 f[i][0] 的计算都是通过前面某个位置的状态 $1$ 来确定的，故可以重新设计状态，将其状态设计为和 $1$ 紧密相关的表示。

状态表示

f[i] 表示在前 $i$ 个烽火台中，点燃第 $i$ 个烽火台的所有方案中最小的代价。

状态转移

根据方法一中的分析，要维护 $i$ 前面长度为 $m$ 的区间的 f 的最小值。

f[i] = min(f[k]) + w[i]，其中 $i - m \le k < i$。

代码实现

状态的设计并不能保证 f[n] 就是最终的结果，因为最优的结果可能是不点燃第 $n$ 个烽火台。

由于不点燃连续的烽火台的长度不能超过 $m$，所以可以维护 $n-m+1 \sim n$ 中的 f 值的最小值即为所求。

代码模板如下所示：

#include <iostream>

using namespace std;

const int N = 200010;
int a[N];
int f[N];
int q[N];
int n, m;

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

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

    int ans = 1e9;
    for(int i = n - m + 1; i <= n; i ++) ans = min(ans, f[i]);

    cout << ans << endl;

    return 0;
}

时间复杂度为 $O(n)$。

方法三：逆向思维（单调队列优化 $DP$）

题意为从 $n$ 个烽火台中点燃若干个，保证不点燃的连续烽火台的长度不超过 $m-1$，求最小的点燃代价。相当于从 $n$ 个烽火台中去掉若干个烽火台，保证去掉的连续烽火台的长度不超过 $m-1$，求去掉的最大代价，最终用 $n$ 个烽火台的总代价减去去掉的最大代价即为所求。

那这个问题就相当于问题 修剪草坪 。

状态表示

f[i] 表示在前 $i$ 个烽火台中选出连续长度不超过 $m-1$ 的所有方案中的最大代价。

状态转移

f[i] = max(f[i-1], f[k-1] + s[i] - s[k])，其中 $i-m < k < i$。

可以看出要维护 $i$ 前面长度为 $m-1$ 区间中 f[k - 1] - s[k] 的最大值，可用单调队列来优化。

代码实现

使用单调队列维护长度为 $m-1$ 区间的 f 的最大值。

最终结果输出 s[n] - f[n]。

代码模板如下：

#include <iostream>

using namespace std;

const int N = 200010;
int s[N];
int f[N];
int q[N];
int n, m;

int get(int i) {
    if(!i) return i;
    return f[i - 1] - s[i];
}

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

    int hh = 0, tt = -1;
    q[++ tt] = 0;

    for(int i = 1; i <= n; i ++) {
        if(i - q[hh] >= m) hh ++;
        f[i] = max(f[i - 1], s[i] + get(q[hh]));

        while(hh <= tt && get(q[tt]) < get(i)) tt --;
        q[++ tt] = i;
    }

    cout << s[n] - f[n] << endl;

    return 0;
}

时间复杂度为 $O(n)$。