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

读题点这里

题目简述

给定一个长度为 $n$ 的序列 $v$ ，初始时，所有元素的值均为 $1$。有 $3$ 种操作可以作用在序列上：

  1. 将 $v_1,v_2,\ldots,v_i$ 的值全部设为 $0$ ，操作的代价是 $a_i$；
  2. 将 $v_i$ 的值设为 $0$ ，操作的代价是 $b_i$；
  3. 将 $v_i$ 的值设为 $1$ ，操作的代价是 $c_i$。

现在有 $q$ 次询问，每次询问给定一个集合 $P$ ，要求将集合 $P$ 中的元素设为 $1$ ，其余位置的值设为 $0$ ，同时要求最小化所有操作的总代价。

思路概述

对于每个询问，我们需要找到一种操作序列，使得序列 $v$ 中下标位于集合 $P$ 的元素的值为 $1$ ，其余位置的值为 $0$ ，并且操作总代价最小。为了实现这个目标，我们可以使用动态规划的方法。

首先，我们定义两个数组 $f$ 和 $g$ ，其中 $f[i]$ 表示在第 $i$ 步操作结束时，序列 $v$ 中下标位于集合 $P$ 的元素的值为 $1$ ，其余位置的值为 $0$ ，且最后一个操作是将下标 $p_i$ 的元素设为 $1$ 的最小代价；$g[i]$ 表示在第 $i$ 步操作结束时，序列 $v$ 中下标位于集合 $P$ 的元素的值为 $1$ ，其余位置的值为 $0$ ，且最后一个操作是将下标 $p_i$ 的元素设为 $0$ 的最小代价。

接下来，我们可以使用动态规划的思想来计算 $f$ 和 $g$ 数组的值。具体来说，对于每个 $i$ ，我们可以通过以下两种方式来计算 $f[i]$ 和 $g[i]$：

  1. 如果我们选择将下标 $p_i$ 的元素设为 $1$ ，则 $f[i]$ 的值为 $a[p_i-1]+g[i-1]$ ，表示在选择这个操作之前，我们已经将下标 $p_i-1$ 之前的元素设为 $1$ ，且最后一个操作是将下标 $p_{i-1}$ 的元素设为 $0$ ，此时我们需要将下标 $p_i$ 的元素设为 $1$ ，所以操作代价为 $a[p_i-1]$ ，再加上前 $i-1$ 步操作的最小代价 $g[i-1]$。
  2. 如果我们选择将下标 $p_i$ 的元素设为 $0$ ，则 $f[i]$ 的值为 $f[i-1]+s[p_i-1]-s[p_{i-1}]$ ，表示在选择这个操作之前，我们已经将下标 $p_{i-1}$ 之前的元素设为 $1$ ，且最后一个操作是将下标 $p_{i-1}$ 的元素设为 $1$ ，此时我们需要将下标 $p_i$ 的元素设为 $0$ ，所以操作代价为 $s[p_i-1]-s[p_{i-1}]$ ，再加上前 $i-1$ 步操作的最小代价 $f[i-1]$。

根据上述思路，我们可以使用动态规划的方法计算出 $f[m]$ 和 $g[m]$ 的值，然后根据题目要求，输出 $g[m]+a[n]$ 和 $f[m]+s[n]-s[p[m]]$ 中的较小值作为第 $i$ 次询问的操作总代价的最小值。

算法步骤

对于每个询问，进行如下操作：

  1. 读入集合 $P$ 的大小 $m$ 和元素值。
  2. 使用动态规划的方法计算 $f[m]$ 和 $g[m]$ 的值：
    • 初始化 $f[0]=g[0]=0$。
    • 对于 $i$ 从 $1$ 到 $m$ ，依次计算 $f[i]$ 和 $g[i]$：
    • 如果选择将下标 $p_i$ 的元素设为 $1$ ，则 $f[i]=a[p_i-1]+g[i-1]$。
    • 如果选择将下标 $p_i$ 的元素设为 $0$ ，则 $f[i]=f[i-1]+s[p_i-1]-s[p_{i-1}]$。
    • $g[i]=g[i-1]+c[p_i]$。
  3. 根据题目要求，输出 $g[m]+a[n]$ 和 $f[m]+s[n]-s[p[m]]$ 中的较小值作为第 $i$ 次询问的操作总代价的最小值。

多测不清空，爆零两行泪。

复杂度

时间复杂度为 $O(n+ \sum m)$。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define N 500005
typedef long long ll;

ll a[N],b[N],c[N],n,q,m;
ll sum[N],p[N],s[N],f[N],g[N];

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%lld",&b[i]);
        s[i]=s[i-1]+b[i];
    }
    for(int i=1;i<=n;++i){
        scanf("%lld",&c[i]);
    }
    for(int i=1;i<=n;++i){
        a[i]=min(a[i],a[i-1]+b[i]);
    }
    scanf("%lld",&q);
    while(q--){
        scanf("%lld",&m);
        for(int i=1;i<=m;++i){
            scanf("%lld",&p[i]);
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            f[i]=min(a[p[i]-1]+g[i-1],f[i-1]+s[p[i]-1]-s[p[i-1]]);
            g[i]=g[i-1]+c[p[i]];
        }
        printf("%lld\n",min(g[m]+a[n],f[m]+s[n]-s[p[m]]));
        for(int i=1;i<=m;++i) g[i]=f[i]=0;
    }
    return 0;
}