读题点这里

题目简述

给定一个长度为 nn 的序列 vv ,初始时,所有元素的值均为 11。有 33 种操作可以作用在序列上:

  1. v1,v2,,viv_1,v_2,\ldots,v_i 的值全部设为 00 ,操作的代价是 aia_i
  2. viv_i 的值设为 00 ,操作的代价是 bib_i
  3. viv_i 的值设为 11 ,操作的代价是 cic_i

现在有 qq 次询问,每次询问给定一个集合 PP ,要求将集合 PP 中的元素设为 11 ,其余位置的值设为 00 ,同时要求最小化所有操作的总代价。

思路概述

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

首先,我们定义两个数组 ffgg ,其中 f[i]f[i] 表示在第 ii 步操作结束时,序列 vv 中下标位于集合 PP 的元素的值为 11 ,其余位置的值为 00 ,且最后一个操作是将下标 pip_i 的元素设为 11 的最小代价;g[i]g[i] 表示在第 ii 步操作结束时,序列 vv 中下标位于集合 PP 的元素的值为 11 ,其余位置的值为 00 ,且最后一个操作是将下标 pip_i 的元素设为 00 的最小代价。

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

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

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

算法步骤

对于每个询问,进行如下操作:

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

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

复杂度

时间复杂度为 O(n+m)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;
}