NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 29 题

2.（烽火传递）烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在某两座城市之间有 $n$ 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续的 $m$ 个烽火台中至少要有一个发出信号。现输入 $n,m$ 和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。

例如，有 $5$ 个烽火台，他们发出信号的代价依次为 $1,2,5,6,2$，且 $m$ 为 $3$，则总共最少花费代价为 $4$，即由第 $2$ 个和第 $5$ 个烽火台发出信号。

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
    pos[SIZE],home[SIZE],opt[SIZE];
    //hep[i]表示用顺序数组储存的堆heap中第i个元素的值
    //pos[i]表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]
    //home[i]表示heap[i]在序列opt中的位置，即opt[home[i]]=heap[i]

void swap(int i,int j)//交换堆中的第i个和第j个元素
{
    int tmp;
    pos[home[i]]=j;
    pos[home[j]]=i;
    tmp=heap[i];
    head[i]=head[j];
    heap[j]=tmp;
    tmp=home[i];
    home[i]=home[j];
    home[j]=tmp;
}
void add(int k)//在堆中插入opt[k]
{
    int i;
    r++;
    heap[r]=        ①      ;
    pos[

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考堆优化DP，核心是把DP转移里的'滑动窗口最小值'用一个小根堆实时维护。拿到题先别急着填空，先手算一个短序列（比如n=5,m=3），把opt数组算出来，再看代码里add/remove堆时每个下标和值的对应关系，就能反推出①②③④⑤⑥该填什么。

最容易栽跟头的是堆里home和pos两个数组的指向搞反——home[i]存的是堆中第i个元素对应哪个opt下标，pos[k]存的是opt[k]在堆里的位置，两者互为逆映射，填反了程序就乱套。其次是窗口删除条件，题目要求连续m个里至少一个发信号，所以窗口左边界是i-m，删除堆顶时要判断home[1]<i-m，很多同学会写成i-m+1导致多删或少删。还有opt[i]的转移里min区间是[i-m,i-1]，很多同学会下意识以为堆顶永远是opt[i-1]，其实堆里装的是所有候选值，必须pop掉过期元素再取堆顶。

题型识别与核心思想

看到'连续的m个烽火台中至少有一个发出信号'，立刻反应过来这是经典的滑动窗口最小值问题。题目要求计算总代价最小，设opt[i]表示'在1..i中做出选择，且第i个烽火台发出信号时的最小总代价'。要使[1..i]合法且第i个发信号，上一个发信号的j必须满足i-j≤m（即j∈[i-m,i-1]），且j可以是0（虚拟烽火台，代价0）。于是转移方程为：

opt[i] = value[i] + min{opt[j] | i-m ≤ j ≤ i-1}

整个DP过程就是不断往窗口里加新的opt值、从窗口里删掉过期的值，同时随时查询窗口最小值。直接枚举min需要O(m)，总复杂度O(nm)，但m可达n，会超时。这里用小根堆维护窗口内的opt值，插入和删除都是O(log n)，整体O(n log n)。堆里存的是opt的值，为了支持'删除任意一个opt[k]'，需要维护三个辅助数组：heap（堆数组）、pos[k]（opt[k]在堆中的下标）、home[i]（堆中第i个位置对应哪个opt下标）。

手算验证（建立直观感受）

用题目给的例子：n=5,m=3，cost=[1,2,5,6,2]。

• opt[0]=0（虚拟）
• opt[1]=1+0=1
• opt[2]=2+min(opt[0..1])=2+0=2
• opt[3]=5+min(opt[0..2])=5+0=5
• opt[4]=6+min(opt[1..3])=6+min(1,2,5)=7
• opt[5]=2+min(opt[2..4])=2+min(2,5,7)=4

最后答案是min(opt[3..5])=4，对应选第2个和第5个烽火台。这个手算结果就是代码要模拟的过程：每次i增加时，先把opt[i]插入堆，再pop掉堆顶所有下标< i-m的元素，然后堆顶就是当前窗口最小值。理解了这个流程，填空就顺理成章了。