P9744 题解（2023 激励计划评分 8）「KDOI-06-S」消除序列 题解

· · 题解

\Large\color{black}\textbf{P9744 「KDOI-06-S」消除序列} \Large\textbf{题解}

\textbf{题目传送门}

\textbf{更好的阅读体验}

\large\textbf{思路}

对于在 i 处执行的第 1 种操作，不如在 i-1 处执行一次操作 1，再在 i 处执行一次操作 2，即 a_i=\min(a_i,a_{i-1}+b_i)。

接下来考虑每一次询问，有几种策略：

最朴素的：在 n 处执行操作 1，使得所有值为 0，再依次在 p_i 的下标处执行操作 3，使得对应位置变为 1，代价为 a_n+\sum_{i\in P} c_{p_i}。

以及：对于每一个 p_i，在第 p_i-1 处执行操作 1，由于 P 升序，可以依次在 P 的 1\sim i-1 项处执行操作 3，使得 p_{i}-1 及其以前的序列 v_1\sim v_{p_i} 都满足条件，单步代价 a_{p_i-1}+\sum_{j=1}^{i-1}c_{p_j}；由于 v_{p_i} 本身即为 1，跳过即可；而后依次在 (p_i+1)\sim n 中不在 P 中的项执行一次操作 2。代价为：

a_{p_i-1}+\sum_{j=1}^{i-1}c_{p_j}+\sum_{j=p_i+1,j\not\in P}^n b_j=a_{p_i-1}+\sum_{j=1}^{i-1}c_{p_j}+\sum_{j=p_i+1}^n b_j-\sum_{j=p_i+1,j\in P}^n b_j

同时，在处理 v_1\sim v_{p_i} 时也可以在 p_i 处执行操作 1，并依次在 P 的 1\sim i 项处执行操作 3，单步代价为 a_{p_i}+\sum_{j=1}^{i}c_{p_j}。综合两种方案，对于每一个 p_i，总代价为：

\min(a_{p_i-1}+\sum_{j=1}^{i-1}c_{p_j},a_{p_i}+\sum_{j=1}^{i}c_{p_j})+\sum_{j=p_i+1}^n b_j-\sum_{j=p_i+1,j\in P}^n b_j

其中，\sum b_i、\sum c_i 以及 \sum b_{p_i} 都可以用前后缀预处理。

\large\textbf{代码} 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5, M = 1e9 + 7;
int n, a[N], b[N], c[N], fb[N], fc[N], fr[N], q, m, p[N];
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) cin>>b[i];
    for(int i = 1; i <= n; i++) cin>>c[i];
    for(int i = n; i >= 1; i--) fb[i] = fb[i + 1] + b[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];
            fc[i] = fc[i - 1] + c[p[i]];
        }
        fr[m + 1] = 0;
        for(int i = m; i >= 1; i--) fr[i] = fr[i + 1] + b[p[i]];
        int ans = a[n] + fc[m];
        for(int i = 1; i <= m; i++) 
            ans = min(ans, min(a[p[i] - 1] + fc[i - 1], a[p[i]] + fc[i]) + fb[p[i] + 1] - fr[i + 1]);
        cout<<ans<<endl;
    }
    return 0;
}