题目描述

n个烽火台，燃起每个烽火台需要一定的费用，并且要求任何一个m区间范围内至少燃起一个，求花费的总代价最小。

样例

输入样例：
5 3
1 2 5 6 2
输出样例：
4

分析：

一共就$1$维，$i$个烽火台, 要有连续的$m$台是条件，要求的是花费的总代价最小。

状态表示为： f[i] 以第i个烽火台结尾，并且满足条件的所有选法的集合。
状态转移： 倒数第二个数是哪一座烽火台，假设是$k$，当然也要满足条件， f[i] = min(f[i], f[k] + w[i]);

没优化的dp 只能过5个数据

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

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

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> w[i];

    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < i; j ++)
            if(i - j <= m)
                f[i] = min(f[i], f[j] + w[i]);

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

单调队列优化

这里处理的是f[i]，它是一个递增的序列，快速找出在给定窗口大小的范围内最小值窗口是i前面的范围为m的区间。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

int f[N], w[N];
int n, m;
int q[N];
int hh = 0, tt = 0;

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> w[i];

    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(q[hh] < i - m) hh ++;
        f[i] = min(f[i], f[q[hh]] + w[i]);
        while(hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++ tt] = i;
    }

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