題目：

題目描述

烽火臺又稱烽燧，是重要的防御設施，一般建在險要處或交通要道上。一旦有敵情發生，白天燃燒柴草，通過濃煙表達信息：夜晚燃燒干柴，以火光傳遞軍情。在某兩座城市之間有?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?范圍內。
1<=n，m<=1,000,000，保證答案在?int?范圍內。

題解：

引用ssoj官方題解：

要用動態規劃的方法解決。
我們可以寫出這樣的方程f[i]:=min{f[j]}+a[i]（i-m<=j<i-1）
因為要保證i之前的3個中必須存在被點亮的烽火臺。單純這樣循環會造成超時。

我們想到了用單調隊列進行優化，由于隨著i的循環，每次只有一個i進入決策區間也只有一個i出決策區間，由于每次選取決策區間中的最小值，所以維護一個單調遞增序列，每次取出隊首元素即可。

為什么可以將隊尾元素無情的刪去呢？由于后進隊的序列同時滿足在原序列中的位置更靠后和其在動態規劃中的價值更大。這樣選取這個元素就要比選取之前的任何一個決策要優，所以之前被刪掉的決策都是無用的。

這道題的本質就是用單調隊列維護了決策本身的價值和其在原序列中位置的同時單調。
要特別注意單調隊列中的值是決策在原決策序列中的位置。

第一次見dp可以用單調隊列搞的····牛逼

代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; const int inf=1e+9; const int N=1e6+5; int n,m,w[N]; int que[N],head,tail,dp[N]; inline int R() { int f=0;char c;for(c=getchar();(c<'0'||c>'9');c=getchar());for(;c>='0'&&c<='9';c=getchar())f=(f<<3)+(f<<1)+c-'0';return f; } int main() {//freopen("a.in","r",stdin);n=R(),m=R();for(int i=1;i<=n;i++)w[i]=R();head=1,tail=1;dp[1]=w[1];que[1]=1;int temp=inf;for(int i=1;i<=m;i++)dp[i]=min(temp,w[i]);for(int i=2;i<=n;i++){if(i>m) dp[i]=dp[que[head]]+w[i];tail++; while(dp[i]<=dp[que[tail-1]]&&tail>head) tail--;que[tail]=i;if(que[tail]-que[head]>=m) head++;}int ans=inf;for(int i=n;i>=n-m+1&&i>=1;i--)ans=min(ans,dp[i]);cout<<ans<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/AseanA/p/7257328.html

總結

以上是生活随笔為你收集整理的刷题总结——烽火传递（单调队列+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。