题目#

link

题解#

考虑dp

设f[i]表示使序列由全是1到满足集合 $P$ 条件所需的最少代价

然后想一想，f[i]怎么推

首先，我们可以把p[i]之前的全部推平，都变成 $0$ ，然后一个一个变成1

其次，我们也可以把f[i - 1]搞出来，然后把p[i - 1] + 1到p[i] - 1之间都弄成 $0$ 。

这里就只能进行若干次第二次操作了，可以用前缀和来优化

但是“首先”一条的复杂度这么做肯定太高，因此再设g[i]表示使序列由全是 $0$ 到满足集合 $P$ 条件所需的最少代价。

状态转移方程在代码里（

锅#

考场上想到有可能要用dp，但没接着想下去。而是想贪心性质去了（但是好像可以用贪心做，等几天看看别的题解）

还真有 https://www.luogu.com.cn/blog/Pretharp/p9744-ti-xie

继而可得，我们需要归零的前缀的末尾必然是在某一个将要变为 1 的位置的前面一个位置，显然可以直接对于每个询问 O(m) 枚举得到答案。时间复杂度 O(n+mq)

代码#

1
#include<bits/stdc++.h>
2
const int N = 5e5 + 10;
3
using namespace std;
4
#define int long long
5
int a[N], b[N], c[N];
6
int n;
7
//O(nq)的算法肯定超时，又因为提供了∑m，所以考虑可以O(qm)のdp
8
int f[N], g[N];//f_i表示把序列[1, 1, 1, 1, 1.....]变成满足前p_i个数所需要的最小代价
9
//但是发现——似乎没法快速转移，于是 令 g_i表示把序列[0, 0, 0, 0, 0.....]变成满足前p_i个数所需要的最小代价
10
int p[N], m;
11
int b_sum[N];
12
signed main()
13
{
14
  scanf("%lld", &n);
15
  for(int i = 1;i <= n;i++)
16
    scanf("%lld", &a[i]);
17
  for(int i = 1;i <= n;i++)
18
    scanf("%lld", &b[i]), b_sum[i] = b_sum[i - 1] + b[i];
19
  for(int i = 1;i <= n;i++)
20
    scanf("%lld", &c[i]);
21

22
  for(int i = 2;i <= n;i++)
23
    a[i] = min(a[i - 1] + b[i], a[i]);
24
  int q;
25
  scanf("%lld", &q);
26

27
  while(q --)
28
  {
29
    scanf("%lld", &m);
30
    for(int i = 1;i <= m;i++)
31
    {
32
      scanf("%lld", &p[i]);
33
    }
34

35
    for(int i = 1;i <= m;i++)
36
    {
37
      g[i] = g[i - 1] + c[p[i]];
38
      f[i] = a[p[i] - 1] + g[i - 1];
39
      f[i] = min(f[i], f[i - 1] + b_sum[p[i] - 1] - b_sum[p[i - 1]]);
40
    }
41
    printf("%lld\n", min(g[m] + a[n], f[m] + b_sum[n] - b_sum[p[m]]));
42
  }
43
  return 0;
44
}