算法提高课汇总

算法思路

本题难点在于状态定义 — 位置$i$确定点燃烽火.

$DP$分析

状态定义$f(i)$

• 集合: 位置$i$点燃烽火的所有合法方案.

• 属性: Min代价

状态计算

$i$点燃烽火, 根据要求在$i - m\sim i - 1$长度为$m$的区间内至少需要点燃一座烽火台,
则$f(i) = min\lbrace f(j) + w(i)\rbrace$, 其中$w(i)$表示点燃$i$座烽火台代价, $i-m\le j\le i-1$.

单调队列

$f(i) = min\lbrace f(j) + w(i)\rbrace = min\lbrace f(j)\rbrace + w(i), i-m\le j\le i-1$.
在长度为$m$的窗口内求$f$最小值 — 单调队列优化.

实现代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

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

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

    int hh = 0, tt = -1; q[++ tt] = 0; //统一计算 加入边界f(0) = 0
    for ( int i = 1; i <= n; i ++ )
    {
        if ( q[hh] < i - m )    hh ++; //超出[i - m, i - 1]的边界
        f[i] = f[q[hh]] + w[i];
        while ( hh <= tt && f[q[tt]] >= f[i] )  tt --;
        q[++ tt] = i;
    }

    int res = INF;
    for ( int i = n - m + 1; i <= n; i ++ ) //最后m个状态均满足题目要求
        res = min(res, f[i]);
    cout << res << endl;

    return 0;
}