题解

这是一个单调队列优化动规问题

---

题目要求：在 $n$个烽火台中，每连续 $m$个烽火台中至少有一个发出信号，求最小总代价。
这可以转化为：选择若干个位置点燃烽火，使得任意两个相邻被选中的位置之间的距离不超过 $m$
（或者更准确地说，对于任意区间 $[i−m+1,i]$，其中至少有一个被选中）。

---

动规状态定义：

设 $f[i]$ 表示：‌前 $i$ 个烽火台满足条件，且第 $i$个烽火台一定发出信号‌时的最小代价。

状态转移方程：

如果第$i$个烽火台发出信号，那么上一个发出信号的烽火台$j$必须满足：$i−j≤m$（即 $j≥i−m$），这样才能保证$j$和$i$之间的烽火台都被覆盖，且不会出现在某段长度为$m$的区间内没有信号的情况。
注意：这里隐含了一个边界处理，通常我们会引入一个虚拟的第$0$号烽火台，代价为$0$，作为起始点。
因此，转移方程为：
$f[i]=a[i]+min _{i−m≤j<i}f[j]$（$f$数组中下标为$i-m$到$i$中的最小值，$j$指的是找最小值时的下标）
其中$a[i]$是第$i$个烽火台的代价。

最终答案：

$ans=min_{n−m+1≤i≤n }{f[i]}$

---

优化：

直接做肯定会超时，我们观察转移方程，要求的是区间最小值，这明显是一个滑动窗口问题
所以我们用一个单调递增队列来维护，复杂度就是$O(n)$

#include<cstdio>
#include<algorithm>
const int N=2e5+10;
int n,m;
int a[N],f[N],q[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int hh=0,tt=0;
    for(int i=1;i<=n;i++){
        if(i-q[hh]>m)hh++;
        f[i]=f[q[hh]]+a[i];
        while(hh<=tt && f[q[tt]]>=f[i])tt--;
        q[++tt]=i;
    }
    int ans=2147483647;
    for(int i=n-m+1;i<=n;i++)ans=std::min(ans,f[i]);
    printf("%d",ans);
    return 0;
}