一本通 1602：烽火传递

题目描述

烽火台是重要的军事防御设施，一般建在交通要道或。
一旦有军情发生，则白天用浓烟，晚上有火光传递军。
在某两个城市之间有n座烽火台，每个烽火台发出信。
为了使情报准确传递，在连续 m
个烽火台中至少要有一个发出信号。
现在输入 n,m
和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入样例

5 3
1 2 5 6 2

输出样例

4

---

算法1

(普通DP)

考虑DP,dp[i][j]表示当前已选至i,其中有j个烽火台没有选.
可得状态转移方程:

f[i]:=min{f[j]}+a[i]（i-m<=j<i-1）

很明显超时。

C++ 代码

不能才不会写呢！

算法2(单调队列优化)

因为要找最小的,就可以想到单调队列,里面存储的值就是到那个点的最小代价.

时间复杂度

能过,(肯定不是因为我算不来才不写(⊙o⊙)…)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int N=1e6+10;
int n,m,l,r;
int a[N],f[N],q[N<<1];
/*
    队列中每个点就是以他自己开头的m个烽火台的最小总代价.
    也可能没有m个,如<m的.
    最后遍历一遍n-m+1~n,取其中最小的.
*/
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    l=r=0;
    for(int i=1;i<=n;i++){
        while(l<r&&i-q[l]>m) l++;//如果不是i个内,就出队.
        f[i]=f[q[l]]+a[i];
        while(l<r&&f[q[r]]>f[i]) r--;
        q[++r]=i;
    }
    int ans=INF;
    for(int i=n-m+1;i<=n;i++) ans=min(ans,f[i]);
    printf("%d",ans);
    return 0;
}