形式化题目

给定长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$ 和正整数 $m$。选出一个下标集合 $S \subseteq \{1, 2, \dots, n\}$，要求对任意 $x$ 满足 $1 \le x \le x + m - 1 \le n$，区间 $[x,\ x+m-1]$ 中都至少有一个元素属于 $S$；求 $\sum_{i \in S} a_i$ 的最小值。

样例：$n = 5,\ m = 3,\ a = (1, 2, 5, 6, 2)$。取 $S = \{2, 5\}$，代价 $2 + 2 = 4$；长度 3 的三个窗口 $\{1,2,3\},\{2,3,4\},\{3,4,5\}$ 分别含 $2$ 或 $5$，全部满足。

正解

思路

1. 把"连续 $m$ 座"改写成位置条件

设选中的下标从小到大为 $p_1 < p_2 < \dots < p_k$。逐个检查每个长度为 $m$ 的窗口就会发现，约束等价于下面三条纯位置条件：

前两条对应前缀窗口：如果 $p_{t+1} - p_t > m$，那么长度为 $m$ 的区间 $[p_t + 1,\ p_t + m]$ 完全落在两个选中点之间、一个选中点都没有，违规。

第三条是尾部豁免，也是本题最容易写错的地方：最后一段 $p_k + 1 \dots n$ 干脆不选任何烽火台也是合法的，只要求它的长度 $n - p_k \le m - 1$（长度不足 $m$ 的段不可能包含任何一个完整的窗口）。这说明答案不能只取"第 $n$ 座点火"的方案。

反过来，只要这三条成立，任意长度 $m$ 的窗口 $[x, x+m-1]$ 一定夹在某两个相邻选中点之间（或两端），若其中无选中点就会违反上述某一条，故约束成立。两边都成立，改写是等价的。

于是问题变成：选一串下标，相邻两项距离不超过 $m$，首项不超过 $m$，末项不小于 $n - m + 1$，最小化代价和。

1
2
3
4a:   1    2    5    6    2        n = 5, m = 3
     #    *    #    #    *        * = 点火（选 2 号、5 号）
      \___________/    |         相邻点火间隔 3 <= m = 3   ✓
                       \___/      尾部 0 座 <= m-1 = 2     ✓  尾部豁免

2. 状态定义与转移

沿着链从左往右推，需要记住的唯一信息是"上一座点火的烽火台在哪"，因为只有它限制了下一座能选多远。于是：

$dp[i]$ = 第 $i$ 座必须点火，且前缀 $1 \dots i$ 已经满足约束时的最小代价。

枚举上一座点火的位置 $j$：它要么不存在（此时必须有 $i \le m$，用虚拟下标 $j = 0$ 概括），要么满足 $i - j \le m$ 即 $j \ge i - m$。固定 $j$ 时前缀 $1 \dots j$ 的最优值恰好是 $dp[j]$（$dp$ 的定义就要求 $j$ 点火，与"$j$ 是上一座"吻合），中间的 $j+1 \dots i-1$ 不点火、不产生代价。所以

$dp[0] = 0$ 是虚拟哨兵，专门负责 $i \le m$ 时"前面一座都不选"的情形：此时 $dp[i] = a_i$。

3. 答案是尾部窗口的最小值

设 $t$ 是最后一座点火的烽火台。$dp[t]$ 里已经含了 $a_t$ 和它之前全部代价，$t$ 之后不再点火，合法性只剩尾部条件 $n - t \le m - 1$，即 $t \ge n - m + 1$。因此

为什么不能直接输出 $dp[n]$：$dp[n]$ 强制第 $n$ 座点火。取 $n = 3,\ m = 3,\ a = (5, 1, 5)$，最优是只点 2 号（代价 1），而 $dp[3] = a_3 + \min(dp[0..2]) = 5 + 0 = 5$。取尾部窗口的 $\min(dp[1..3]) = \min(5, 1, 6) = 1$ 才对。

4. 滑动窗口最小值：单调队列

朴素地对每个 $i$ 枚举窗口里的 $j$ 是 $O(nm)$，在 $n = m = 2 \times 10^5$ 时最坏约 $4 \times 10^{10}$ 次运算，必须消除这个瓶颈。注意窗口

随 $i$ 右移，左右端点都单调不减、长度固定为 $m$，这正是滑动窗口最小值：用单调队列可以均摊 $O(1)$ 得到窗口最小值。队列里存下标，并维持

队列中的 $dp$ 值自队首到队尾严格递增，于是队首就是窗口最小值。

每步按固定顺序做三件事：

1. 过期：把所有 $< i - m$ 的队首弹出（它们已经不在窗口里）。
2. 取最小值：dp[i] = dp[队首] + a[i]。
3. 入队：先比较 dp[i] 与 dp[队尾]，把队尾所有 $\ge dp[i]$ 的下标弹出再让 $i$ 入队。被弹掉的下标比 $i$ 更靠左（更早过期）且不更优，永远不会再成为任何窗口的最小值，淘汰是安全的。

主循环结束后队列里剩下的就是"还没过期"的那些下标，此时把过期阈值改成 $n-m+1$ 再弹一次队首，队首即答案。每个下标入队一次、至多出队一次，总复杂度 $O(n)$。

5. 样例演算

按 main.py 的定义逐步演算 $a=(1,2,5,6,2),\ m=3$。窗口 是 $j$ 的合法范围 $[\max(0,i-m),\ i-1]$，队首 / 队首 dp 是弹出过期元素后单调队列的头部，队列 是入队 $i$ 之后的状态。

三点值得注意：

• 第 4 步下标 0 过期（$0 < 4-3$），队首换成 1，$dp$ 值从 0 变 1，这才让 $dp[4] = 1 + 6 = 7$ 而不是 $0 + 6$；
• 第 5 步 $dp[5] = a_5 + dp[2] = 2 + 2 = 4$，$dp[2] = 2$ 对应"前缀里只点 2 号"，加上 5 号就是样例方案 $\{2, 5\}$；
• 第 5 步入队时，队尾 $dp[4] = 7 \ge dp[5] = 4$，于是 4 被弹掉——同一时刻 4 更靠左却更贵，留它没有意义。

最后做尾部筛选：$n - m + 1 = 3$，队列 $[2, 5]$ 中下标 2 过期，队首变 5，答案 $dp[5] = 4$，与样例一致。（$\min(dp[3..5]) = \min(5,7,4) = 4$ 也印证了公式。）

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:10
# update_at: 2026-09-30 21:10

import sys
from collections import deque

INF = 1 << 60  # 不可达状态的初值：比任何合法代价都大，用作单调队列的初始地板


def min_cost(n: int, m: int, cost: list[int]) -> int:
    """在前 n 座烽火台上选出「任意连续 m 座至少选一座」的最小总代价。

    记 dp[i] 为「第 i 座必须点火，且前缀 [1, i] 已经满足约束」的最小代价。
    i 与 i-1 之间最多隔 m-1 座不点，所以上一个点火位置落在 [i-m, i-1]，
    于是 dp[i] = a[i] + min(dp[i-m .. i-1])：滑动窗口取最小值，用单调队列做到均摊 O(1)。
    """
    # 位置 0 是虚拟哨兵：滑到 i = 1 时它正好离开窗口，代表「前面一段没点火也不越界」。
    dp = [INF] * (n + 1)
    dp[0] = 0
    window = deque([0])  # 存下标，对应 dp 值自队首到队尾单调不减

    for i in range(1, n + 1):
        while window[0] < i - m:  # 队首滑出左界 i-m，不再能作为转移来源
            window.popleft()
        dp[i] = dp[window[0]] + cost[i - 1]
        while window and dp[window[-1]] >= dp[i]:  # 更晚进队却更优，旧的下标永远没用
            window.pop()
        window.append(i)

    # 尾部没有强制点火的烽火台：最后一座点火的 j 只要满足 n - j <= m-1，
    # 即 j >= n-m+1，剩下的 j+1..n 就都不超过 m-1 座，同样合法。
    # 下界再和 1 取大：m > n 时整条链不足 m 座，答案退化为「选最便宜的一座」，
    # 否则会把哨兵 dp[0]=0 当成合法结尾，误输出 0。
    while window[0] < max(1, n - m + 1):
        window.popleft()
    return dp[window[0]]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    cost = [next(data) for _ in range(n)]
    print(min_cost(n, m, cost))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:07
 * update_at: 2026-10-05 12:07
 */
// 烽火传递：单调队列优化的线性 DP。
// 约束等价于「相邻两座点火台的距离不超过 m，且最后一座离 n 不超过 m-1」，
// 于是 dp[i] = a[i] + min(dp[i-m .. i-1])，答案是 min(dp[n-m+1 .. n])。
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

ll a[MAXN];    // a[i] 第 i 座烽火台发出信号的代价
ll dp[MAXN];   // dp[i] 表示第 i 座必须点火、且前缀 1..i 已满足约束时的最小代价
ll que[MAXN];  // 单调队列，存下标；对应的 dp 值自队首到队尾严格递增
int head, tail; // 队列区间 [head, tail)，队首 que[head] 即窗口最小值所在下标

int main() {
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    // 下标 0 是虚拟哨兵，dp[0] = 0，负责 i <= m 时「前面一座都不点火」的情形
    dp[0] = 0;
    head = 0;
    tail = 0;
    que[tail++] = 0;

    for (int i = 1; i <= n; i++) {
        while (head < tail && que[head] < i - m) {
            head++; // 队首已经滑出窗口左界 i-m，不能再作为转移来源
        }
        dp[i] = dp[que[head]] + a[i];
        // 更晚进队却更优的旧下标永远不会再成为最小值，直接淘汰
        while (head < tail && dp[que[tail - 1]] >= dp[i]) {
            tail--;
        }
        que[tail++] = i;
    }

    // 尾部豁免：最后一座点火台 t 只需满足 n - t <= m-1，即 t >= n-m+1，
    // 所以答案不是 dp[n]。下界与 1 取大，兼顾 m > n 时退化为选最便宜的一座
    ll low = max(1LL, n - m + 1);
    while (head < tail && que[head] < low) {
        head++;
    }
    printf("%lld\n", dp[que[head]]);
    return 0;
}

复杂度

• 时间复杂度：$O(n)$。读入 $O(n)$；主循环执行 $n$ 次，每次至多一次队首弹出、一次队首查询、均摊一次队尾弹出，全部是均摊 $O(1)$；每个下标入队 1 次、出队至多 1 次，所以总操作数是 $O(n)$ 量级的常数倍。相比朴素 $O(nm)$ 的最坏 $4 \times 10^{10}$，$n = 2 \times 10^5$ 时不到 $10^6$ 次基本操作。
• 空间复杂度：$O(n)$。dp 与代价数组各 $n + 1$ 个整数，单调队列至多存 $m + 1$ 个下标。实测峰值内存 $\le 25$ MB，远低于 128 MB 限制。

总结

• 关键的建模动作是把"任意连续 $m$ 座至少一座"翻译成相邻选中点距离 $\le m$，并单独记住尾部 $m-1$ 座可以不选这条不对称的豁免。
• 有了"相邻距离受限"的认识，状态只需要记"上一座点火台在哪"，得到 $dp[i] = a_i + \min_{j \in [i-m,\ i-1]} dp[j]$；虚拟哨兵 $dp[0] = 0$ 统一处理 $i \le m$ 的情形。
• 答案是 $\min_{t \ge n-m+1} dp[t]$ 而不是 $dp[n]$，因为最后一座点火台不必是第 $n$ 座。
• 窗口左右端点都单调右移，是滑动窗口最小值问题；单调队列保持队内 $dp$ 递增，队首即最小值，把 $O(nm)$ 的枚举降到均摊 $O(1)$，总复杂度 $O(n)$。
• 边界：$m = 1$ 时窗口只含 $i-1$，答案退化为 $\sum a_i$；$m \ge n$ 时整个链都不足 $m$，答案退化为 $\min a_i$。

图示解析

这张图串起从题面到答案的推理主线：

1
2
3
4
5
6任意连续 m 座至少一座点火
`- 等价改写：相邻选中点距离 <= m，首位 <= m，末位 >= n-m+1（尾部豁免）
   `- 沿链 DP：dp[i] = 第 i 座必点火时前缀的最小代价
      `- dp[i] = a_i + min(dp[i-m .. i-1])：固定长度的滑动窗口最小值
         `- 单调队列：窗口左右端点单调右移，队首即最小值，均摊 O(1)
            `- ans = min(dp[n-m+1 .. n])，O(n) 结束

顺着每一层看：第一层把"窗口覆盖"这种二维说法压成一维的位置条件，第二层的"尾部豁免"提示答案不是 $dp[n]$，第三层把转移写成区间最小值，第四层才是具体的数据结构选择。图只给出骨架，最后一层的逐步推进细节以上面的样例 DP 表为准。