找了好半天也沒(méi)找到可以注冊(cè)&&提交本題得OJ润歉，
所以不能保證AC。
描述
烽火臺(tái)又稱(chēng)烽燧套硼，是重要的防御設(shè)施卡辰，一般建在險(xiǎn)要處或交通要道上琴许。一旦有敵情發(fā)生绪撵，白天燃燒柴草隙赁，通過(guò)濃煙表達(dá)信息：夜晚燃燒干柴杨拐，以火光傳遞軍情馒胆。在某兩座城市之間有n個(gè)烽火臺(tái)擎鸠，每個(gè)烽火臺(tái)發(fā)出信號(hào)都有一定的代價(jià)睦焕。為了使情報(bào)準(zhǔn)確的傳遞红省，在m個(gè)烽火臺(tái)中至少要有一個(gè)發(fā)出信號(hào)〔卟耍現(xiàn)輸入n晶疼、m和每個(gè)烽火臺(tái)發(fā)出的信號(hào)的代價(jià)酒贬，請(qǐng)計(jì)算總共最少需要花費(fèi)多少代價(jià)，才能使敵軍來(lái)襲之時(shí)翠霍，情報(bào)能在這兩座城市之間準(zhǔn)確的傳遞６Ф帧！寒匙！
輸入格式 Input Format
第一行有兩個(gè)數(shù)n,m分別表示n個(gè)烽火臺(tái)零如，在m個(gè)烽火臺(tái)中至少要有一個(gè)發(fā)出信號(hào)。
第二行為n個(gè)數(shù)锄弱，表示每一個(gè)烽火臺(tái)的代價(jià)考蕾。
輸出格式 Output Format
一個(gè)數(shù)，即最小代價(jià)会宪。
樣例
5 3
1 2 5 6 2
4
時(shí)間限制 Time Limitation
各個(gè)測(cè)試點(diǎn)1s
注釋 Hint
1<=n,m<=1,000,000
題解：
一維線性dp肖卧，看上去是一眼秒得題。
dp[i]表示傳到第i個(gè)峰臺(tái)并且點(diǎn)亮了它時(shí)用的總最小代價(jià)掸鹅。
dp[i] = min(dp[i-m]塞帐。。河劝。壁榕。。dp[i-1]) + a[i]
（如果i-m到i-1中一個(gè)都沒(méi)有點(diǎn)亮赎瞎，那顯然這m個(gè)就不符合題中：【每m個(gè)至少亮一個(gè)】的要求了）
最后dp[n-m+1]牌里。。务甥。牡辽。dp[n]中最小的一個(gè)即為所求。
但是我們注意到n敞临、m都是1e6的范圍态辛。
那么這個(gè)的O(n*m)的算法就GG了。
但注意到整個(gè)過(guò)程挺尿，很像滑動(dòng)窗口那道題奏黑，即每m個(gè)窗口中我們要選擇最小的那個(gè)值和a[i]相加來(lái)更新dp[i].
我們只需要維護(hù)一個(gè)單增的隊(duì)列，隊(duì)列元素為峰臺(tái)下標(biāo)编矾，當(dāng)前點(diǎn)第i盞燈時(shí)熟史，i-m以前的都沒(méi)用了，不能用他們更新窄俏，所以pop_front蹂匹。
然后隊(duì)首即為這m個(gè)中的最小代價(jià)，用它更新dp[i]凹蜈，上一個(gè)思路的O(m)部分就省下來(lái)了限寞。
然后在把i加入隊(duì)列之前忍啸，把比它大的值都pop_back掉，因?yàn)橛肋h(yuǎn)用不到它們來(lái)更新了履植，畢竟有離得更近计雌，代價(jià)更低的第i盞。
復(fù)雜度：每個(gè)元素最多進(jìn)出一次隊(duì)列玫霎，所以并沒(méi)有什么要擔(dān)心的白粉。O(n)。
用單調(diào)隊(duì)列優(yōu)化的dp方法有一定的規(guī)律性鼠渺，簡(jiǎn)單來(lái)說(shuō)就是可以看出滑動(dòng)窗口的影子。
即有單調(diào)性眷细。一定范圍內(nèi)只會(huì)用一個(gè)數(shù)組中的最大值或者最小值拦盹。
比較有名的應(yīng)用應(yīng)該是在優(yōu)化多重背包的時(shí)候。
后面會(huì)更新到用單純形法優(yōu)化dp溪椎，算是更加神奇的所在普舆，在我OR(運(yùn)籌學(xué))的學(xué)習(xí)中也有所應(yīng)用。
#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
deque<LL> q;
LL dp[maxn];
LL a[maxn];
int n,m;
void init(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n ; i++)
scanf("%lld",&a[i]);
q.push_back(0);
}
LL ans = 1e14+10;
void sov(){
for(int i = 1 ; i <= n ; i++){
//printf("i = %d\n",i);
for(auto j:q){
if(j < i-m && i-m >= 0)
q.pop_front();
}
// for(auto j:q){
// printf("inqueue: %d\n",j);
// }
LL k = q.front();
dp[i] = dp[k]+a[i];
while(dp[q.back()]>dp[i]) q.pop_back();
q.push_back(i);
}
for(int i = n-m+1 ; i <= n ; i++){
ans = min(ans,dp[i]);
}
printf("%lld\n",ans);
}
int main(){
init();
sov();
}
