烽火传递
【题目描述】
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递！！！
【输入描述】
第一行有两个数n,m（1<=n,m<=1000000)分别表示n个烽火台，在m个烽火台中至少要有一个发出信号。
第二行为n个数，表示每一个烽火台的代价。
【输出描述】
一个数，即最小代价。
【样例输入】
5 3
1 2 5 6 2
【样例输出】
4
分析：
多增加两个点表示两座城市，将它们看做代价为0的烽火台，然后很容易得到这个式子：
f[i]:=min(f[j])+a[i](i-m<=j<i)
然后用单调队列优化，队列元素保存f数组的值，维护单调递增队列，每次取队头即可。
代码1（DP+单调队列）：
program fire;
var
f,a,b,g:array[..]of longint;
n,i,m,h,t:longint;
procedure work(x:longint);
begin
t:=t+; b[t]:=f[x]; g[t]:=x;
while (b[t]<=b[t-])and(t>h) do
begin
t:=t-; b[t]:=b[t+]; g[t]:=g[t+];
end;
if x-g[h]=m then h:=h+;
end;
begin
assign(input,'fire.in');
reset(input);
assign(output,'fire.out');
rewrite(output);
readln(n,m);
for i:= to n do
read(a[i]);
n:=n+;
f[]:=; b[]:=;g[]:=;h:=; t:=;
for i:= to n do
begin
f[i]:=b[h]+a[i];
work(i);
end;
writeln(f[n]);
close(input); close(output);
end.
也可以用堆来优化，每次取的时候判断根节点是否超出范围，超出则删除，继续判断，直到符合要求。
代码2（DP+堆）：
program fire;
var
f,a,b,g:array[..]of longint;
n,i,m,t:longint;
function get(x:longint):longint;
var i,s,tmp:longint;
begin
while (x-g[]>m)and(t>) do
begin
b[]:=b[t]; g[]:=g[t];t:=t-;
i:=;
while (i*<=t)or(i*+<=t) do
begin
if (i*+>t)or(b[i*]<b[i*+]) then s:=i* else s:=i*+;
if b[i]>b[s] then
begin
tmp:=b[i]; b[i]:=b[s]; b[s]:=tmp;
tmp:=g[i]; g[i]:=g[s]; g[s]:=tmp;
i:=s;
end else break;
end;
end;
get:=b[];
end;
procedure put(x:longint);
var s,tmp:longint;
begin
t:=t+;b[t]:=f[x];g[t]:=x; s:=t;
while (s<>)and(b[s div ]>b[s]) do
begin
tmp:=b[s div ]; b[s div ]:=b[s]; b[s]:=tmp;
tmp:=g[s div ]; g[s div ]:=g[s]; g[s]:=tmp; s:=s div ;
end;
end;
begin
assign(input,'fire.in');
reset(input);
assign(output,'fire.out');
rewrite(output);
readln(n,m);
for i:= to n do
read(a[i]);
n:=n+;
f[]:=; b[]:=;g[]:=; t:=;
for i:= to n do
begin
f[i]:=get(i)+a[i];
put(i);
end;
writeln(f[n]);
close(input); close(output);
end.