題目描述
烽火台又稱烽燧，是重要的防禦設施，一般建在險要處或交通要道上。一旦有敵情發生，白天燃燒柴草，通過濃煙表達資訊：夜晚燃燒幹柴，以火光傳遞軍情。在某兩座城市之間有 n 個烽火台，每個烽火台發出信号都有一定的代價。為了使情報準确的傳遞，在 m 個烽火台中至少要有一個發出信号。現輸入 n、m 和每個烽火台發出的信号的代價，請計算總共最少需要多少代價，才能使敵軍來襲之時，情報能在這兩座城市之間準确的傳遞！
輸入格式
第一行有兩個數 n，m 分别表示 n 個烽火台，在任意連續的 m 個烽火台中至少要有一個發出信号。
第二行為 n 個數，表示每一個烽火台的代價。
輸出格式
一個整數，即最小代價。
樣例資料 1
輸入
5 3
1 2 5 6 2
輸出
4
備注
【資料範圍】
1<=n，m<=1,000,000，保證答案在 int 範圍内。
分析
單調隊列
定義： f[i]-->第 i 位發出信号，且前面都滿足要求的最小代價
轉移：f[i]=min{f[j]}+a[i] (i-m<=j<i)
那麼由于轉移的時候隻和前面 m 個位置有關系，且是取這個區間内的最小值
我們就不用O（n*m）來轉移了
發現每次 i 調大最多隻允許多一個 j 進入決策區間，最多隻有一個 j 退出決策區間
我們可以用線段樹來維護區間的最小值，這是O（n log m ）的，但常數有點大啊……
我們也可以用單調隊列（想象為一個視窗，每次隻允許 m 個數出現）來維護目前決策區間的最小值
這樣就是O（1）尋找最小值的了
（注意單調隊列中保證下标遞增，對應的值也遞增（或遞減））
還有一些小細節要注意，寫在代碼裡了
代碼
#include<bits/stdc++.h>
#define in read()
#define N 1000009
using namespace std;
inline int read(){
char ch;int f=1,res=0;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return f==1?res:-res;
}
int n,m,a[N],q[N],head=1,tail=1;//注意tail一定要賦為1，因為前m個位置隻用算自己
int f[N];
//f[i]-->第 i 位發出信号，且前面都滿足要求的最小代價
//f[i]=min{f[j]}+a[i] (i-m<=j<i)
int main(){
n=in;m=in;
int i,j;
for(i=1;i<=n;++i){
a[i]=in;
while(head<=tail&&i-q[head]>m) ++head;
f[i]=f[q[head]]+a[i];
while(head<=tail&&f[i]<=f[q[tail]]) tail--;
q[++tail]=i;
}
int res=(1ll<<31)-1;
for(i=n-m+1;i<=n;++i) res=min(res,f[i]);
cout<<res;
return 0;
}