「KDOI-06-S」消除序列 题解

wxzzzz · 2023-10-15 19:11:24 · 题解

思路

• update 2023.10.15 更正一处笔误，感谢 @lwx20211103 的指正。

动态规划。

一些定义：

首先可以初步的更新一下 a_i，看看是不是用某个 a_{x-1}+\displaystyle\sum_{j=x}^i b_j 代替 a_i 更优。有转移方程 a_i=\min(a_i,a_{i-1}+b_i)。

考虑 g_i，显然有 g_i=g_{i-1}+c_{p_i}。

考虑 f_i，有两种可能：

1. 把 p_{i-1}\sim p_i 中的所有 1 变为 0，代价为 f_{i-1}+\displaystyle{\sum_{j=p_{i-1}}^{p_i}}b_j，其中 \displaystyle{\sum_{j=p_{i-1}}^{p_i}}b_j 可以用前缀和维护。

2. 把 1\sim p_i 全部更改为 0，然后再改，代价为 a_{p_i-1}+g_{i-1}。

但是，p_m 不一定为 n，还要考虑把 p_m+1\sim n 的元素全部变为 0，和转移 f 类似的，最终答案为 \min(g_m+a_n,f_m+\displaystyle{\sum_{j=p_m+1}^{n}}b_j)。

代码

#include <bits/stdc++.h>
using namespace std;
int n, q, m, a[1000005], b[1000005], c[1000005], p[1000005];
long long s[1000005], g[1000005], f[1000005];
int main() {
    cin >> n;

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

    for (int i = 1; i <= n; i++)
        cin >> b[i], s[i] = s[i - 1] + b[i];

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

    for (int i = 1; i <= n; i++)
        a[i] = min(a[i], a[i - 1] + b[i]);

    cin >> q;

    while (q--) {
        cin >> m;

        for (int i = 1; i <= m; i++)
            cin >> p[i];

        for (int i = 1; i <= m; i++) {
            g[i] = g[i - 1] + c[p[i]];
            f[i] = a[p[i] - 1] + g[i - 1];
            f[i] = min(f[i], f[i - 1] + s[p[i] - 1] - s[p[i - 1]]);
        }

        cout << min(g[m] + a[n], f[m] + s[n] - s[p[m]]) << '\n';
    }

    return 0;
}