Description

烽火臺又稱烽燧，是重要的軍事防御設施，一般建在險要或交通要道上。一旦有敵情發生，白天燃燒柴草，通過濃煙表達信息；夜晚燃燒干柴，以火光傳遞軍情，在某兩座城市之間有 n 個烽火臺，每個烽火臺發出信號都有一定代價。為了使情報準確地傳遞，在連續 m 個烽火臺中至少要有一個發出信號。請計算總共最少花費多少代價，才能使敵軍來襲之時，情報能在這兩座城市之間準確傳遞。

Input

第一行：兩個整數 N，M。其中N表示烽火臺的個數， M 表示在連續 m 個烽火臺中至少要有一個發出信號。接下來 N 行，每行一個數 Wi，表示第i個烽火臺發出信號所需代價。

Output

一行，表示答案。

Sample Input

5 3
1
2
5
6
2

Sample Output

4

Hint

對于50%的數據，M≤N≤1,000 。
對于100%的數據，M≤N≤100,000，Wi≤100。

.
.
.
.
.
.
分析
動態轉移方程：
f[i]=min(f[j])(i-m<j<i) +a[i]

尋找最小值可用單調隊列優化，f[i-1]為要插入的數據

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;int n,m,a[100001],f[100001],q[200001];int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&a[i]);int head=1,tail=1;for (int i=1;i<=n;i++){while (head<=tail&&f[q[tail]]>=f[i-1]) tail--;tail++;q[tail]=i-1;while (head<=tail&&(i-1)-q[head]+1>m) head++;f[i]=f[q[head]]+a[i];}int ans=2147483647;for (int i=n-m+1;i<=n;i++)ans=min(ans,f[i]);printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10292787.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的烽火传递的全部內容，希望文章能夠幫你解決所遇到的問題。

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