烽火传递

dp 单调队列 线性dp 烽火传递 - LibreOJ 10180 - Virtual Judge (csgrandeur.cn) 烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晩上有火光传递军情。 在某两个城市之间有 $n$ 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 $m$ 个烽火 台中至少要有一个发出信号。现在输入 $n,m$ 和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。

输入格式

第一行是 $n,m$ ，表示 $n$ 个烽火台和连续烽火台数 $m$ ； 第二行 $n$ 个整数表示每个烽火台的代价 $a_i$ 。

输出格式

输出仅一个整数，表示最小代价。

样例

5 3
1 2 5 6 2

4

对于全部数据， $1\le n,m\le 2\times 10^5,1\le a_i\le 1000$ 。

思路

一维线性问题通常都可以进行子问题划分, 这里则用类似于最长上升子序列问题LST的状态划分方式。

状态表示： f[i] 1-i中选, 结尾为i且选中的最小价值 状态计算： f[i] = min(f[j] + w[i]) j in [i - m,i-1] 对于$i$所在的$m$区间是合法的, 能转移到i且保证合法的区间是 $[i-m,i-1]$ 即$i$之前的长度为$m$区间内选一个, 不然会导致i所在区间和前一个区间中间有遗漏

显然这里我们没必要真的用双重循环, 因为选中的是最小值, 且是在i之前m长度中的任意一个, 即区间最值问题。 使用单调队列优化。

\begin{eqnarray} f_{i} & = & \min \left\{f_{j}+w_{i}\right\} & (0 \leq i-j-1 \leq m-1) \\ \Rightarrow & f_{i} & = w_{i}+\min \left\{f_{j}\right\} &(1 \leq i-j \leq m) \end{eqnarray}

结果状态为$res=f_i(n-m+1\le i\le n)$ 也可以利用单调队列的特性, 最后是枚举到 [n - m, n - 1]这个区间, 若q[hh] < n + 1 - m , 则hh++, 那么 f[q[hh]] 就是答案。

这里用$tt=0$, 是因为需要计算$f[1]$, 把$a[0]$先入队, 避免出现$a[1]-a[1]$的起始问题

队头边界条件为 $q[hh]<i-m$ 是因为区间总长度带上$i$是$m+1$, 而 $i-q[hh]$ 所计算的区间长度是实际长度减一, 故条件为 $i-q[hh]+1>m+1$, 化简一下就是 $i-q[hh]>m$
总结一下：
在i之前长度为$m$的区间是 $i-q[hh]>m$, 包含$i$长度为$m$的区间是$i-q[hh]>=m$
在i之前长度为$m+1$的区间是 $i-q[hh]>m+1$, 包含$i$长度为$m+1$的区间是$i-q[hh]>=m+1$
若题目是小于$m$的区间, 则替换为$m-1$即可。

代码

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int q[N], hh, tt;
int f[N];
int n, m;
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    hh = 0, tt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (q[hh] < i - m)
            hh++;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i])
            tt--;
        q[++tt] = i;
    }
 
    if (n - m + 1 > q[hh])
        hh++;
    cout << f[q[hh]] << endl;
    return 0;
}