烽火传递 题解

做法：单调队列优化dp。

设表示在放烽火台使区间合法的最小花费。
有方程
对于用单调队列维护即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int f[N], n, m, a[N];
deque<int>q;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    q.push_back(0); f[0] = 0;
    for(int i = 1; i <= n; ++i) {
        while(!q.empty() && i - q.front() > m) q.pop_front();
        f[i] = f[q.front()] + a[i];
        while(!q.empty() && f[q.back()] > f[i]) q.pop_back();
        q.push_back(i); 
    }
    int ans = 0x3f3f3f3f;
    for(int i = n; i > n - m; --i) ans = min(ans, f[i]);
//    for(int i = 1; i <= n; ++i) printf("%d ", f[i]); puts("");
    printf("%d\n", ans);
}