题目描述

烽火台是重要的军事防御设施，一般建在交通要道或险要处。

一旦有军情发生，则白天用浓烟，晚上有火光传递军情。

在某两个城市之间有$n$座烽火台，每个烽火台发出信号都有一定的代价。

为了使情报准确传递,在连续$m$个烽火台中至少要有一个发出信号。

现在输入$n,m$和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入格式

第一行是两个整数 n,m，具体含义见题目描述；

第二行 n 个整数表示每个烽火台的代价 ai。

输出格式

输出仅一个整数，表示最小代价。

数据范围

$1≤n,m≤2×10^5$,
$0≤a_i≤1000$

输入样例

5 3
1 2 5 6 2

输出样例

4

暴力枚举TLE——时间复杂度$O(nm)$

状态表示：①集合:$f[i]$表示$1$~$i$个灯塔满足条件时，并且$i$点亮。②属性：最小代价
状态计算：$f[i]=min(f[k]+w[i])$ ( $i-m≤k≤i-1$)
答案：$(n-m+1)$~$n$必须有灯塔亮，所以枚举一下求出最小值即可

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int f[N];
int w[N],n,m;
int main()
{
    memset(f,0x3f,sizeof f);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int k=max(0,i-m);k<i;k++) 
            f[i]=min(f[i],f[k]+w[i]);

    int res=0x3f3f3f3f;
    for(int i=n+1-m;i<=n;i++) res=min(res,f[i]);
    cout<<res<<endl;
    return 0;
}

单调队列优化——时间复杂度$O(n)$

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int f[N];
int w[N],n,m;
int q[N],tt=-1,hh=0;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    q[++tt]=0;//假设城市算作一个编号为0且代价为0的灯塔
    for(int i=1;i<=n;i++)
    {
        if(tt>=hh&&i-q[hh]>m) hh++;
        f[i]=f[q[hh]]+w[i];
        while(tt>=hh&&f[q[tt]]>=f[i])tt--;
        q[++tt]=i;
    }
    int res=0x3f3f3f3f;
    for(int i=n+1-m;i<=n;i++) res=min(res,f[i]);//同样城市也算一个代价为0的灯塔，城市前m的灯塔至少有个点亮
    cout<<res<<endl;
}