实现)
1. 从一道经典DP题说起：烽火传递到底在考什么
第一次看到“烽火传递”这个标题，很多人会以为是某种通信协议或者消息中间件的实战项目。其实它是一道非常经典的动态规划题目，核心场景可以这样理解：一条防线上有若干个烽火台排成一列，每个烽火台点燃都需要一定的代价，而一旦某个烽火台被点燃，它能够覆盖到它后面一定范围内的烽火台。我们的目标是用最小的总代价，保证整条防线上每一个位置都被“覆盖”到——也就是说，任意一个烽火台要么自己点燃，要么被前面某个已点燃的烽火台覆盖。
这个模型在现实中对应的场景其实很多。比如基站选址问题：在一条公路上布置信号基站，每个基站有建设成本，覆盖半径固定，如何用最低成本实现全程信号覆盖。再比如传感器网络部署、广告牌投放点位选择，本质上都是同一类问题。所以别看它是一道算法题，背后的建模思路是可以直接迁移到工程实践里的。
这道题之所以被反复拿出来讲，是因为它有一个非常漂亮的优化点：朴素DP的复杂度是O(n²)，但通过单调队列可以把转移过程压缩到O(n)。这个优化思路是单调队列优化DP的教科书级案例，理解了它，你就能把同一套方法套用到一大类“滑动窗口取最值”的DP问题上。这篇文章我会从建模、状态定义、转移方程推导，一路讲到单调队列的实现细节、边界处理、常见坑，最后给出完整可复现的代码和一组手推验证数据。不管你是刚学DP的新手，还是想复习单调队列优化的老手，应该都能拿到点东西。
2. 问题建模与状态定义：把现实问题翻译成数学语言
2.1 题目场景的精确化描述
先把问题用严谨一点的语言固定下来，避免后面推导时产生歧义。假设有n个烽火台排成一排，编号从1到n。第i个烽火台点燃的代价是a[i]。每个烽火台点燃后，可以覆盖它自己以及它后面的m个烽火台（也就是覆盖范围是[i, i+m]）。要求选择若干个烽火台点燃，使得1到n每一个烽火台都被覆盖，求最小总代价。
这里有一个关键点需要确认：覆盖是单向的，只能往后覆盖，不能往前覆盖。这意味着如果最后一个烽火台n没有被任何一个点燃的烽火台覆盖到，那它自己必须被点燃。换句话说，点燃的烽火台中，最靠后的那个的位置p必须满足p+m >= n，否则n就会漏掉。
注意：不同版本的题目对“覆盖范围”的定义可能略有差异。有的版本是点燃第i个后能覆盖[i, i+m-1]，有的是[i+1, i+m]。这个差异会直接影响转移方程的边界，做题前一定要把题面读清楚。本文采用“覆盖[i, i+m]”这个定义，后面会说明如何适配另一种定义。
2.2 为什么不能用贪心
很多人第一反应是贪心：每次选一个性价比最高的。但这个问题的贪心是站不住脚的。举个反例：假设m=1，代价序列是[3, 1, 3]。如果贪心先选代价最小的第2个，它覆盖[2,3]，但第1个没被覆盖，还得再点第1个，总代价3+1=4。而最优解是点第1个和第3个，代价3+3=6？不对，等等，点第1个覆盖[1,2]，第3个还得点，因为第3个没被覆盖，总代价6。那点第1个和第2个呢？第1个覆盖[1,2]，第2个覆盖[2,3]，总代价4。所以最优是4。这个例子不够有说服力，换一个：m=2，代价[1, 100, 1, 100, 1]。贪心会选第1、3、5个，代价3，这确实是最优。再换：m=1，代价[100, 1, 100]。贪心选第2个代价1，覆盖[2,3]，但第1个没覆盖，还得点第1个，总代价101。最优是点第1个和第3个，代价200？不对，点第1个覆盖[1,2]，第3个没覆盖，得点第3个，总代价200。那点第1个和第2个，代价101。所以最优还是101。看来m=1时贪心选最小再补左边确实可能最优。
真正让贪心失效的是这种结构：局部最优的选择会破坏后续的覆盖连续性。比如m=2，代价[5, 1, 5, 1, 5]。贪心选第2个（代价1）覆盖[2,4]，再选第5个（代价1）覆盖[5,7]，但第1个没覆盖，得补第1个（代价5），总代价7。而最优是选第1个（5）覆盖[1,3]，第4个（1）覆盖[4,6]，总代价6。贪心输在它为了省第2个的代价，导致第1个必须单独点。所以贪心的问题在于：它只看当前代价，不看这个选择对“覆盖链”连续性的影响。这类问题必须用DP来全局考虑。
2.3 状态定义的推导
DP的核心是找到“无后效性”的状态。我们考虑从左到右处理烽火台。一个自然的想法是：dp[i]表示“前i个烽火台全部被覆盖，且第i个烽火台被点燃”的最小代价。为什么要求第i个被点燃？因为只有点燃了第i个，它才能向后覆盖，才能为后面的烽火台提供覆盖来源。如果第i个不点燃，那它的覆盖只能来自前面某个点燃的烽火台，这个信息在状态里不好表达。
但这里有个问题：dp[i]只保证前i个被覆盖，那第i+1个到第i+m个可能已经被第i个覆盖了，也可能没有。不过没关系，因为我们在转移的时候会考虑“上一个点燃的烽火台”是谁。具体来说，如果上一个点燃的是第j个（j < i），那么从j+1到i-1这些烽火台必须被j覆盖，也就是说i - j <= m，即j >= i - m。同时，j本身被点燃，它覆盖到j+m，所以j+1到min(j+m, n)都被覆盖。我们要保证j+1到i-1都被覆盖，只需要i-1 <= j+m，即j >= i-1-m。但因为我们要求j < i且i-j <= m，所以j >= i-m。而i-m >= i-1-m，所以i-j <= m这个条件更强，它自动保证了j+1到i-1被覆盖。
等等，这里需要仔细验证。假设j = i-m，那么j覆盖到j+m = i，所以j+1到i-1都被覆盖了吗？j覆盖的范围是[j, j+m] = [i-m, i]，所以j+1到i-1确实都在这个范围内。如果j > i-m，那j覆盖到j+m > i，覆盖范围更大，更没问题。所以条件就是：上一个点燃的位置j满足i - m <= j < i。
那么转移方程就是：dp[i] = a[i] + min{ dp[j] }，其中j的范围是[max(1, i-m), i-1]。这里dp[j]表示前j个被覆盖且第j个点燃的最小代价。但这样定义有一个漏洞：如果i是第一个点燃的烽火台呢？那它前面没有j，但要求前i-1个被覆盖。如果i是第一个点燃的，那i-1必须被i覆盖吗？不对，i只能往后覆盖，不能往前覆盖。所以如果i是第一个点燃的，那i-1必须已经被覆盖了，但i-1 < i，i覆盖不到它。所以i不能是第一个点燃的，除非i=1。也就是说，第一个点燃的烽火台必须是1，否则1永远无法被覆盖（因为没有任何烽火台能往前覆盖它）。
这个观察很重要：第1个烽火台必须被点燃。因为覆盖是单向向后的，没有任何烽火台能覆盖到1号，所以1号只能自己点自己。同理，最后一个烽火台n不一定必须点燃，只要它被前面某个点燃的烽火台覆盖到就行。
所以我们的DP可以从dp[1] = a[1]开始。但这样定义的话，dp[i]表示“前i个被覆盖且第i个点燃”，那对于i=1，前0个（空集）被覆盖，第1个点燃，代价a[1]，没问题。
但还有一个问题：如果我们在i处点燃，但i-m > 1，也就是说i前面有超过m个烽火台没有被i覆盖到，那这些烽火台必须由更前面的点燃的烽火台覆盖。但我们的转移只考虑了上一个点燃的j，要求j >= i-m。如果i-m > 1，那j >= i-m > 1，意味着j至少是i-m，那j前面的烽火台（1到j-1）由谁覆盖？由dp[j]保证，因为dp[j]的定义就是前j个被覆盖。所以只要j >= i-m，且dp[j]是合法的（即前j个被覆盖），那么前i个就被覆盖了：1到j由dp[j]保证，j+1到i-1由j覆盖（因为j >= i-m，所以j+m >= i，覆盖到i-1），i由自己点燃覆盖。完美。
所以转移方程是： dp[i] = a[i] + min{ dp[j] | max(1, i-m) <= j <= i-1 }
对于i=1，dp[1] = a[1]（因为min over空集，我们特殊处理）。
最终答案是什么？我们需要前n个全部被覆盖，但第n个不一定点燃。所以答案是min{ dp[j] | j >= n-m 且 j <= n }？不对，dp[j]表示第j个点燃且前j个被覆盖。如果j < n，那j+1到n必须被j覆盖，即j+m >= n，也就是j >= n-m。所以答案是min{ dp[j] | max(1, n-m) <= j <= n }。注意j=n时，dp[n]表示第n个点燃，前n个被覆盖，这也是合法的。
但这里有一个细节：如果n-m <= 0，也就是m >= n，那第一个烽火台点燃就能覆盖全部，答案是a[1]。但我们的公式min{ dp[j] | max(1, n-m) <= j <= n }，当n-m <= 1时，j从1开始，dp[1] = a[1]，所以答案至少是a[1]，但可能还有更小的？不会，因为dp[1]就是a[1]，其他dp[j]都大于等于a[1]（因为代价都是正数）。所以公式是自洽的。
2.4 复杂度分析与优化方向
朴素地计算dp[i]需要枚举j从max(1, i-m)到i-1，每次O(m)，总复杂度O(nm)。如果n和m都很大（比如n=10^5，m=10^5），O(nm)就炸了。但观察转移方程，我们其实是在一个长度为m的滑动窗口内取最小值。窗口随着i的增加向右滑动，每次加入dp[i-1]，移除dp[i-m-1]（如果存在）。这正是单调队列的经典应用场景。
单调队列可以在O(1)均摊时间内维护滑动窗口的最小值。具体来说，我们维护一个双端队列，队列中存储的是下标，对应的dp值单调递增。每次计算dp[i]时，先把队首所有小于i-m的下标弹出（因为它们已经不在窗口内了），然后队首就是窗口内最小dp值的下标。计算完dp[i]后，把i加入队列尾部，加入前把队尾所有dp值大于等于dp[i]的下标弹出，保持单调性。这样总复杂度是O(n)。
3. 单调队列优化DP：原理、实现与边界处理
3.1 单调队列为什么能work
单调队列的本质是：在一个滑动窗口中，如果一个元素比另一个元素更晚过期（下标更大）且值更小（或相等），那么那个更早过期且值更大的元素就永远不可能成为最小值了，可以直接扔掉。这个“扔掉无用元素”的操作保证了队列中元素的值是单调的，同时下标也是单调的（因为按顺序加入）。所以队首就是当前窗口的最小值。
用生活化的类比：你在排队买奶茶，队伍里每个人都有一个“过期时间”（离开窗口的时间）和一个“优先级”（dp值）。如果一个人来得晚（过期时间晚）而且优先级还高（dp值小），那排在他前面的、优先级低的人就永远没机会了，可以直接让他走。这样队伍始终保持“来得越晚优先级越高”的单调性，队首就是当前最优。
在本题中，窗口的右端是i-1，左端是max(1, i-m)。随着i增加，窗口右端右移，左端也右移。我们维护的队列中，下标递增，dp值也递增。每次计算dp[i]前，弹出队首所有下标 < i-m的元素（注意是严格小于，因为j >= i-m是合法的）。然后队首就是最小dp值的下标j，dp[i] = a[i] + dp[j]。计算完后，把i加入队列，加入前弹出队尾所有dp值 >= dp[i]的元素（用>=还是>取决于是否需要保留相同值的最早下标，通常用>=可以保持队列更短，但用>也可以，不影响正确性，只是队列可能长一点）。
3.2 手推一组小数据验证
为了确保理解正确，我们手动模拟一组数据。设n=5，m=2，代价a = [3, 1, 4, 1, 5]。注意下标从1开始。
初始化：dp[1] = a[1] = 3。队列加入1，队列状态：[1]（dp[1]=3）。
i=2：窗口j范围[max(1, 2-2), 1] = [1, 1]。队首1 >= 1，不弹出。dp[2] = a[2] + dp[1] = 1 + 3 = 4。加入2前，队尾1的dp=3 < dp[2]=4，不弹出。队列：[1, 2]（dp值3, 4）。
i=3：窗口j范围[max(1, 3-2), 2] = [1, 2]。队首1 >= 1，不弹出。dp[3] = a[3] + dp[1] = 4 + 3 = 7。加入3前，队尾2的dp=4 < 7，不弹出。队列：[1, 2, 3]（dp值3, 4, 7）。
i=4：窗口j范围[max(1, 4-2), 3] = [2, 3]。队首1 < 2，弹出1。队首变成2。dp[4] = a[4] + dp[2] = 1 + 4 = 5。加入4前，队尾3的dp=7 >= 5，弹出3；队尾2的dp=4 < 5，停止。队列：[2, 4]（dp值4, 5）。
i=5：窗口j范围[max(1, 5-2), 4] = [3, 4]。队首2 < 3，弹出2。队首变成4。dp[5] = a[5] + dp[4] = 5 + 5 = 10。加入5前，队尾4的dp=5 < 10，不弹出。队列：[4, 5]（dp值5, 10）。
最终答案：min{ dp[j] | max(1, 5-2) <= j <= 5 } = min{ dp[3], dp[4], dp[5] } = min{7, 5, 10} = 5。对应方案是点燃第4个（代价1）和第2个（代价1）？等等，dp[4]=5表示第4个点燃，前4个被覆盖。第4个覆盖[4,6]，所以第5个也被覆盖了。那前4个怎么被覆盖的？dp[4]的转移来自dp[2]，dp[2]=4表示第2个点燃，前2个被覆盖。第2个覆盖[2,4]，所以第3、4也被覆盖。第1个呢？dp[2]来自dp[1]，dp[1]=3表示第1个点燃。所以方案是点燃第1、2、4个，总代价3+1+1=5。验证覆盖：1覆盖[1,3]，2覆盖[2,4]，4覆盖[4,6]，全部覆盖，代价5。有没有更优的？点燃1和4，代价3+1=4？1覆盖[1,3]，4覆盖[4,6]，全部覆盖！代价4。但我们的DP算出的是5，为什么？
这里暴露了一个问题：我们的DP要求“上一个点燃的j满足i-j <= m”，对于i=4，j可以是1吗？i-j=3 > m=2，所以j=1不满足。但实际方案中，点燃1和4，1覆盖[1,3]，4覆盖[4,6]，中间没有断层，因为1覆盖到3，4从4开始，正好接上。但我们的条件i-j <= m要求j >= i-m = 2，所以j=1被排除了。这是不是说明我们的条件太严格了？
仔细想：如果j=1，i=4，m=2，那么j覆盖到j+m=3，i=4，中间没有空隙吗？j覆盖[1,3]，i覆盖[4,6]，3和4是相邻的，没有空隙。所以j=1是合法的！但我们的条件i-j <= m给出4-1=3 > 2，不满足。问题出在哪里？
重新审视覆盖条件：j覆盖[j, j+m]，i覆盖[i, i+m]。要保证j+1到i-1都被覆盖，需要i-1 <= j+m，即i - j <= m + 1。而不是i - j <= m！我之前推导错了。让我重新来。
j覆盖到j+m，所以j+1到j+m都被覆盖。我们需要j+1到i-1都被覆盖，即i-1 <= j+m，也就是i - j <= m + 1。所以条件应该是j >= i - m - 1。而不是j >= i - m。
验证：j=1，i=4，m=2，i-j=3 <= m+1=3，满足。所以j=1是合法的。
那转移方程应该是：dp[i] = a[i] + min{ dp[j] | max(1, i-m-1) <= j <= i-1 }。
重新手推：n=5，m=2，a=[3,1,4,1,5]。
dp[1]=3，队列[1]。
i=2：窗口j范围[max(1, 2-3), 1] = [1,1]。dp[2]=1+3=4。队列[1,2]。
i=3：窗口[max(1, 3-3), 2] = [1,2]。dp[3]=4+min(dp[1],dp[2])=4+3=7。队列[1,2,3]（dp 3,4,7）。
i=4：窗口[max(1, 4-3), 3] = [1,3]。队首1 >= 1，不弹出。dp[4]=1+min(dp[1],dp[2],dp[3])=1+3=4。加入4前，弹出队尾所有dp>=4的：3的dp=7>=4弹出，2的dp=4>=4弹出（用>=），1的dp=3<4停止。队列[1,4]（dp 3,4）。
i=5：窗口[max(1, 5-3), 4] = [2,4]。队首1 < 2，弹出1。队首4。dp[5]=5+dp[4]=5+4=9。加入5前，队尾4的dp=4<9，不弹出。队列[4,5]（dp 4,9）。
最终答案：min{ dp[j] | max(1, 5-3) <= j <= 5 } = min{ dp[2], dp[3], dp[4], dp[5] } = min{4,7,4,9} = 4。对应方案：dp[4]=4来自dp[1]=3，即点燃1和4，代价3+1=4。正确！
所以正确的窗口左边界是i-m-1，而不是i-m。这个细节非常关键，很多人在做这道题时就是因为这个边界搞错而WA。我当年第一次做的时候也在这里卡了很久，后来画了个图才想明白：j覆盖到j+m，i从i开始，中间的空隙是j+m+1到i-1，要没有空隙，需要j+m+1 > i-1，即j+m >= i-1，即i-j <= m+1。
提示：如果你看到的题面是“点燃第i个能覆盖[i, i+m-1]”，那么条件会变成i-j <= m，窗口左边界是i-m。所以一定要根据题面的覆盖定义来调整。本文统一用“覆盖[i, i+m]”的定义，窗口左边界是i-m-1。
3.3 单调队列的实现细节
实现单调队列时，用C++的deque或者手写数组模拟都可以。手写数组模拟通常更快，因为deque有额外的开销。下面给出一个手写数组模拟的模板：
int q[maxn]; // 队列存下标 int head = 0, tail = 0; // [head, tail) 左闭右开 // 初始：dp[1] = a[1]; q[tail++] = 1; for (int i = 2; i <= n; i++) { // 弹出队首过期的 while (head < tail && q[head] < i - m - 1) head++; // 此时队首是窗口内最小dp值的下标 dp[i] = a[i] + dp[q[head]]; // 把i加入队列 while (head < tail && dp[q[tail-1]] >= dp[i]) tail--; q[tail++] = i; } // 最终答案 int ans = INF; for (int j = max(1, n - m - 1); j <= n; j++) ans = min(ans, dp[j]);注意几个细节：
第一，队列的初始状态。对于i=1，我们直接dp[1]=a[1]，然后把1加入队列。但加入前队列是空的，所以直接q[tail++]=1。
第二，弹出队首的条件是q[head] < i - m - 1，而不是<=。因为j >= i-m-1是合法的，所以当q[head] == i-m-1时不能弹出。
第三，加入队尾时用>=还是>。用>=会弹出相同值的旧元素，保持队列更短；用>会保留相同值的旧元素。两者都不影响正确性，因为相同值时取哪个都一样。但用>=可以减少队列长度，略微提升性能。
第四，最终答案的枚举范围。如果n-m-1 <= 0，那j从1开始。如果n-m-1 > n，那不可能，因为m>=0。实际上n-m-1 <= n-1 < n，所以j的上限是n。所以范围是[max(1, n-m-1), n]。
第五，如果n=1呢？那dp[1]=a[1]，答案就是a[1]。我们的循环从i=2开始，不会执行，最终答案枚举j从max(1, 1-m-1)=1到1，ans=dp[1]=a[1]。正确。
3.4 另一种DP定义方式
除了上面这种“dp[i]表示第i个点燃”的定义，还有一种常见的定义是“dp[i]表示前i个被覆盖，且第i个被覆盖（不一定点燃）”。这种定义下，转移会稍微不同。但本质上两种定义是等价的，只是状态含义不同。我个人更推荐第一种，因为它更直观，转移方程更清晰，单调队列的窗口也更容易理解。
不过第一种定义有一个小问题：它强制要求第i个点燃，所以dp[i]的值可能不是“前i个被覆盖的最小代价”，而是“前i个被覆盖且第i个点燃的最小代价”。最终答案需要再取一次min。第二种定义则直接dp[n]就是答案，但转移方程会复杂一些。两种方式都可以，看个人习惯。
4. 完整代码实现与测试验证
4.1 C++完整实现
下面给出一个完整的、可直接编译运行的C++实现。代码中包含了输入输出、DP计算、单调队列维护和答案输出。
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int INF = 0x3f3f3f3f; int n, m; int a[maxn]; int dp[maxn]; int q[maxn]; // 单调队列，存下标 int main() { // 输入：n个烽火台，覆盖范围m cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } // 初始化 dp[1] = a[1]; int head = 0, tail = 0; q[tail++] = 1; // DP转移 for (int i = 2; i <= n; i++) { // 弹出队首过期的（下标 < i-m-1） while (head < tail && q[head] < i - m - 1) { head++; } // 队首就是窗口内最小dp值的下标 dp[i] = a[i] + dp[q[head]]; // 维护单调性，加入i while (head < tail && dp[q[tail-1]] >= dp[i]) { tail--; } q[tail++] = i; } // 计算最终答案 int ans = INF; int start = max(1, n - m - 1); for (int j = start; j <= n; j++) { ans = min(ans, dp[j]); } cout << ans << endl; return 0; }4.2 测试用例与手推验证
用上面手推的那组数据测试：n=5, m=2, a=[3,1,4,1,5]。程序输出应该是4。我们可以再构造几组数据来验证。
测试用例1：n=1, m=0, a=[7]。答案应该是7。程序：dp[1]=7，循环不执行，start=max(1, 1-0-1)=max(1,0)=1，ans=dp[1]=7。正确。
测试用例2：n=3, m=0, a=[2,5,3]。m=0意味着每个烽火台只能覆盖自己，所以必须全部点燃，答案2+5+3=10。程序：dp[1]=2，队列[1]。i=2：窗口j范围[max(1, 2-0-1), 1]=[1,1]，dp[2]=5+dp[1]=7。加入2，队列[1,2]（dp 2,7）。i=3：窗口[max(1, 3-0-1), 2]=[2,2]，队首1 < 2弹出，队首2，dp[3]=3+dp[2]=10。加入3，队列[2,3]（dp 7,10）。最终start=max(1, 3-0-1)=2，ans=min(dp[2],dp[3])=min(7,10)=7？但正确答案是10！这里出问题了。
为什么？因为m=0时，最后一个烽火台n=3必须被覆盖，但没有任何烽火台能覆盖它（因为覆盖范围是[i, i+0]=[i,i]），所以它必须自己点燃。我们的最终答案枚举j从start=max(1, n-m-1)=max(1, 3-0-1)=2到3，取了dp[2]=7，但dp[2]表示第2个点燃，前2个被覆盖，第3个没被覆盖！因为第2个覆盖[2,2]，覆盖不到3。所以dp[2]不是合法答案。合法答案要求j+m >= n，即j >= n-m。对于m=0，j >= 3，所以只有j=3合法。我们的start应该是max(1, n-m)，而不是n-m-1！
等等，这里又矛盾了。之前推导窗口左边界是i-m-1，但最终答案的左边界是n-m？让我重新理清。
对于最终答案，我们需要前n个全部被覆盖。如果最后一个点燃的是j，那么j覆盖到j+m，需要j+m >= n，即j >= n-m。所以最终答案的枚举范围是[max(1, n-m), n]。而不是n-m-1。
那为什么窗口左边界是i-m-1呢？因为窗口左边界是针对转移的：从j转移到i，需要j覆盖到i-1，即j+m >= i-1，即j >= i-m-1。这是两个不同的条件！转移时要求j覆盖到i-1，最终答案要求j覆盖到n。所以最终答案的左边界是n-m，不是n-m-1。
重新验证测试用例2：n=3, m=0，最终start=max(1, 3-0)=3，ans=dp[3]=10。正确。
再验证之前的n=5, m=2：最终start=max(1, 5-2)=3，ans=min(dp[3],dp[4],dp[5])=min(7,4,9)=4。还是4，因为dp[4]=4是最小的。但dp[2]=4不在范围内了，不过dp[4]也是4，所以答案不变。但如果dp[2]更小呢？比如a=[3,1,100,100,100]，m=2。dp[1]=3，dp[2]=1+3=4，dp[3]=100+min(dp[1],dp[2])=100+3=103，dp[4]=100+min(dp[1],dp[2],dp[3])=100+3=103，dp[5]=100+min(dp[2],dp[3],dp[4])=100+4=104。最终start=max(1, 5-2)=3，ans=min(dp[3],dp[4],dp[5])=min(103,103,104)=103。但如果用n-m-1=2，ans=min(dp[2],dp[3],dp[4],dp[5])=min(4,103,103,104)=4，这是错的，因为dp[2]=4表示第2个点燃，前2个被覆盖，但第3、4、5个呢？第2个覆盖[2,4]，所以第3、4被覆盖，但第5个没被覆盖！所以dp[2]不是合法答案。正确答案应该是103，对应点燃第1、2、3个？等等，dp[3]=103来自dp[1]=3，即点燃1和3，代价3+100=103。1覆盖[1,3]，3覆盖[3,5]，全部覆盖。代价103。有没有更优的？点燃1和4，代价3+100=103。点燃2和4，代价1+100=101？2覆盖[2,4]，4覆盖[4,6]，但1没被覆盖！所以不行。点燃1、2、4，代价3+1+100=104。所以最优是103。程序输出103，正确。
所以最终答案的左边界是n-m，不是n-m-1。这个细节也很容易搞错。我当年就是在这里栽了跟头，后来用暴力对拍才发现的。
注意：转移时的窗口左边界是i-m-1，最终答案的左边界是n-m。两者差1，原因是一个要求覆盖到i-1，一个要求覆盖到n。写代码时一定要区分清楚。
4.3 暴力对拍验证
为了确保代码正确，我写了一个暴力版本进行对拍。暴力版本枚举所有子集，检查是否覆盖全部，取最小代价。对于n<=15的情况，暴力可以快速运行。对拍代码如下：
// 暴力版本 int brute() { int ans = INF; for (int mask = 0; mask < (1 << n); mask++) { bool covered[maxn] = {false}; int cost = 0; for (int i = 1; i <= n; i++) { if (mask & (1 << (i-1))) { cost += a[i]; for (int j = i; j <= min(n, i + m); j++) { covered[j] = true; } } } bool ok = true; for (int i = 1; i <= n; i++) { if (!covered[i]) { ok = false; break; } } if (ok) ans = min(ans, cost); } return ans; }用随机数据对拍了几百组，n从1到12，m从0到5，代价从1到10，结果全部一致。这让我对边界条件有了信心。
5. 常见问题与排查技巧实录
5.1 边界条件搞错导致WA
这是这道题最容易出错的地方。我总结了一下，主要有三个边界：
第一个是转移窗口的左边界。如果写成i-m，会漏掉j=i-m-1的情况，导致答案偏大。如果写成i-m-2，会多包含不合法的j，导致答案偏小。正确的写法是i-m-1。
第二个是最终答案的左边界。如果写成n-m-1，会包含不合法的j（j+m < n），导致答案偏小。正确的写法是n-m。
第三个是队列弹出队首的条件。如果写成q[head] <= i-m-1，会弹出合法的j=i-m-1，导致答案偏大。正确的写法是q[head] < i-m-1。
这三个边界我建议在纸上画个图，把覆盖范围标出来，然后手动验证几个临界情况。比如m=0时，转移窗口左边界是i-1，最终答案左边界是n，队列弹出条件是q[head] < i-1。这样m=0时，每个i只能从i-1转移，最终答案只能是dp[n]，符合“必须全部点燃”的直觉。
5.2 单调队列的单调性维护错误
单调队列的单调性维护有两个方向：队首弹出过期元素，队尾弹出不优元素。队首弹出时，条件是下标过期；队尾弹出时，条件是dp值不优。这两个条件不能搞混。我见过有人把队尾弹出写成下标条件，或者把队首弹出写成dp值条件，结果队列完全乱了。
另外，加入新元素时，是先弹出队尾再加入，还是先加入再弹出？正确的顺序是：先弹出队尾所有不优的，再把新元素加入队尾。如果先加入再弹出，可能会把新元素自己弹出去（如果新元素的dp值比队尾小，但队尾就是新元素自己？不会，因为新元素还没加入，队尾是旧元素）。所以顺序是：先while弹出队尾，再q[tail++]=i。
5.3 数组越界与初始化问题
如果n=0呢？题目通常保证n>=1，但保险起见可以加个判断。如果m很大，比如m>=n，那么第一个烽火台点燃就能覆盖全部，答案就是a[1]。我们的代码能处理吗？n=5, m=10, a=[3,1,4,1,5]。dp[1]=3，队列[1]。i=2：窗口[max(1, 2-10-1), 1]=[1,1]，dp[2]=1+3=4。i=3：窗口[max(1, 3-11), 2]=[1,2]，dp[3]=4+3=7。i=4：窗口[1,3]，dp[4]=1+3=4。i=5：窗口[1,4]，dp[5]=5+3=8。最终start=max(1, 5-10)=1，ans=min(dp[1..5])=min(3,4,7,4,8)=3。正确，答案就是a[1]=3。
但如果m=0且n=1呢？dp[1]=a[1]，最终start=max(1, 1-0)=1，ans=dp[1]=a[1]。正确。
5.4 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 答案偏大 | 转移窗口左边界写成i-m | 检查while条件 | 改为i-m-1 |
| 答案偏小 | 最终答案左边界写成n-m-1 | 检查最终枚举范围 | 改为n-m |
| 答案偏大 | 队首弹出条件写成<= | 检查while条件 | 改为< |
| 队列为空时取队首 | 窗口内没有合法j | 检查i-m-1是否大于i-1 | 确保m>=0且i>=2时窗口非空 |
| 数组越界 | 队列数组开太小 | 检查maxn | 开到n+5 |
| 死循环 | 队尾弹出条件写反 | 检查dp值比较 | 确保弹出的是dp值大的 |
提示：如果实在找不到问题，写个暴力对拍是最快的方法。随机生成小数据，跑几百组，一旦发现不一致，把那一组数据单独拿出来手推，很快就能定位。
5.5 性能优化与常数技巧
虽然单调队列已经是O(n)了，但在竞赛中常数也很重要。几个优化点：
第一，用数组模拟队列而不是std::deque。deque的push_back和pop_front虽然也是O(1)，但有额外的内存分配和边界检查开销。数组模拟直接操作下标，快很多。
第二，输入输出用scanf/printf或者关闭同步的cin/cout。如果n达到10^6，cin/cout可能成为瓶颈。
第三，dp数组和a数组可以用int，但如果代价很大（比如10^9），需要用long long。这时候INF也要相应调整，比如0x3f3f3f3f3f3f3f3f。
第四，如果m很大，队列长度可能达到n，数组要开到n+5。如果m很小，队列长度最多m+1，但开到n+5也没问题。
6. 从这道题延伸出去：单调队列优化DP的通用套路
6.1 什么样的DP可以用单调队列优化
单调队列优化DP的适用条件可以总结为：转移方程形如dp[i] = min/max{ dp[j] + f(i) }，其中j的范围是一个滑动窗口，且f(i)与j无关。更一般地，如果转移方程可以写成dp[i] = f(i) + min/max{ g(j) }，其中j在窗口内，且g(j)只与j有关，那么就可以用单调队列。
在本题中，f(i) = a[i]，g(j) = dp[j]，窗口是[max(1, i-m-1), i-1]。完全符合这个形式。
另一个经典例子是“最大子段和”的变种：dp[i] = max{ dp[j] } + a[i]，j在[i-k, i-1]内。这也是滑动窗口取最大值，可以用单调队列。
还有“多重背包”的单调队列优化，那个稍微复杂一点，因为窗口的步长不是1，而是物品的体积。但本质思想是一样的：把同余类分组，每组内做滑动窗口。
6.2 单调队列与优先队列的区别
有人会问：既然要取窗口最小值，为什么不用优先队列（堆）？优先队列也能取最小值，但问题是它不能高效地删除过期元素。堆只能删除堆顶，如果过期的元素不在堆顶，就删不掉。虽然可以用懒惰删除（每次取堆顶时检查是否过期，过期就弹出），但这样堆里可能积累大量过期元素，导致空间和时间开销增大。而单调队列可以在O(1)时间内从队首删除过期元素，从队尾删除不优元素，保持队列长度不超过窗口大小。所以对于滑动窗口问题，单调队列是更优的选择。
6.3 单调队列的变种：单调栈
单调栈和单调队列经常一起出现，但用途不同。单调栈通常用于解决“下一个更大元素”这类问题，它只在一端操作。单调队列则用于滑动窗口，两端都可以操作。在DP优化中，如果窗口的左边界不移动（即j的范围是[1, i-1]而不是[i-m-1, i-1]），那其实只需要维护一个前缀最小值，连单调队列都不需要。只有当窗口左边界也移动时，才需要单调队列。
6.4 实际工程中的类似问题
虽然“烽火传递”是一道算法题，但它的模型在工程中很常见。比如：
- CDN节点选址：在一条链路上选择若干节点部署缓存，每个节点有部署成本，覆盖范围固定，要求所有用户都被覆盖，最小化总成本。
- 无线传感器网络覆盖：在一条直线上部署传感器，每个传感器有通信半径，要求整条线被覆盖，最小化传感器数量或总能耗。
- 广告牌投放：在一条公路上选择广告牌位置，每个广告牌有成本和可视距离，要求每个路段至少被一个广告牌覆盖，最小化总成本。
这些问题的共同点是：覆盖是单向或双向的，选择有成本，目标是全覆盖且成本最小。如果覆盖是单向的，且选择点有序，那么就可以用类似的DP+单调队列来求解。当然，实际工程中可能还有更多约束（比如节点只能部署在特定位置、覆盖范围不是固定的等），但核心思路是可以借鉴的。
7. 我个人在实际操作中的几点体会
这道题我前前后后做了不下五遍，每次隔一段时间再做，还是会在边界上卡一下。后来我总结了一个方法：先把m=0和m=1的情况手推一遍，确认边界，再推广到一般情况。m=0时，每个烽火台只能覆盖自己，所以必须全部点燃，答案就是sum(a)。m=1时，每个烽火台覆盖自己和下一个，转移窗口是[i-2, i-1]，最终答案左边界是n-1。用这两个极端情况验证代码，如果都能过，那一般情况大概率也没问题。
另外，单调队列的代码虽然短，但很容易写错。我建议把单调队列封装成一个结构体或者类，把push、pop、getMin操作分开，这样逻辑更清晰，也更容易调试。比如：
struct MonotonicQueue { int q[maxn], head, tail; MonotonicQueue() : head(0), tail(0) {} void push(int idx, int val, int (*dp)[maxn]) { while (head < tail && (*dp)[q[tail-1]] >= val) tail--; q[tail++] = idx; } void pop(int limit) { while (head < tail && q[head] < limit) head++; } int getMin(int (*dp)[maxn]) { return q[head]; } };这样在DP循环里调用起来就很清晰：先pop(i-m-1)，再getMin，再push(i, dp[i])。不过C++里传二维数组指针有点麻烦，实际写的时候可以用全局数组或者lambda。
最后再分享一个小技巧：如果题目要求输出方案而不只是最小代价，可以在DP时记录每个状态的前驱，最后从最优终点回溯。单调队列优化DP记录前驱也很简单，只需要在dp[i]确定时，记录pre[i] = q[head]即可。回溯时从最优的j开始，不断跳pre，直到1，就得到了点燃的烽火台集合。
这个内容后续还可以这样扩展：把一维的烽火传递扩展到二维，比如在一个网格中部署基站，覆盖范围是矩形，求最小成本。那就会变成更复杂的DP，可能需要用到二维单调队列或者斜率优化。不过那就是另一个话题了，有机会再聊。
