烽火传递——单调队列优化dp问题

烽火传递

定义状态：
fi:第i个点燃状态下，从1-i的最小花费，从前fi-m中转移过来。
每次求最小，所以阔以用单调队列进行优化。

代码：

#include 
using namespace std;
const int N = 2e5+10;

int n,m;
int w[N];
int f[N];
int q[N];

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++) scanf("%d",&w[i]);

    int hh = 0, tt = 0;//先放入f[0]进行转移
    for(int i =1;i<=n;i++){
        if(q[hh]<i-m) hh++;
        f[i] = f[q[hh]] +w[i];
        while(hh<=tt&&f[q[tt]]>=f[i]) tt--;
        q[++tt] = i;
    }
    int res = 1e9;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29