LOJ 10180. 烽火传递

十月 29, 2020 1707

题意简述

给定一个数轴，上面有 n 个点，选中每个点有一定代价，现要求连续的 m 个点中至少选一个，求最小代价。

解题思路

考虑 dp。

设 f[i] 表示选第 i 个来保证 [1, i] 这个区间合法的最小代价。

转移方程：

f[i] = \min_{i - m + 1\leq j < i}\{f[j]\} + \mathrm{cost}(i)

可以发现， \min_{i - m + 1\leq j < i}\{f[j]\} 这东西的形式长得比较像滑动窗口，窗口长度为 m，求最小值。

这就是一种 dp 优化：单调队列优化 dp，利用 dp 决策的单调性来优化转移。

代码实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

/**
 *
 * 考虑 dp
 * 设 dp[i] 表示选择第 i 个来保证 [1, i] 合法的最小花费
 * 转移方程：
 * dp[i] = cost[i] + min{dp[j]} (i - m <= j < i)
 * 后面这个 min 可以滑动窗口优化
 *  
 */

const int MAXN = 2e5 + 10;

int q1[MAXN], q2[MAXN];
int h1 = 1, t1 = 1, h2 = 1, t2 = 1; // 左闭右开

int n, m;
int ss[MAXN];
int dp[MAXN];

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) ss[i] = read();
    for (int i = 1; i <= n; ++i) {
        // 队尾弹出不优的，维护单调性
        while (h1 != t1 && q1[t1 - 1] >= dp[i - 1]) --t1, --t2;
        // 队尾入队
        q1[t1++] = dp[i - 1]; q2[t2++] = i - 1;
        // 队头弹出过期的
        while (h2 != t2 && q2[h2] < i - m) ++h1, ++h2;
        // 更新答案
        dp[i] = ss[i] + q1[h1];
    }
    int ans = 0x7f7f7f7f;
    for (int i = n - m + 1; i <= n; ++i) ans = std::min(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}