題目#
題解#
考慮 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，但沒接著想下去。而是想貪心性質去了（但是好像可以用貪心做，等幾天看看別的題解）
繼而可得，我們需要歸零的前綴的末尾必然是在某一個將要變為 1 的位置的前面一個位置，顯然可以直接對於每個詢問 O (m) 枚舉得到答案。時間複雜度 O (n+mq)
代碼#
#include<bits/stdc++.h>
const int N = 5e5 + 10;
using namespace std;
#define int long long
int a[N], b[N], c[N];
int n;
//O(nq)的算法肯定超時，又因為提供了∑m，所以考慮可以O(qm)のdp
int f[N], g[N];//f_i表示把序列[1, 1, 1, 1, 1.....]變成滿足前p_i個數所需要的最小代價
//但是發現——似乎沒法快速轉移，因此 令 g_i表示把序列[0, 0, 0, 0, 0.....]變成滿足前p_i個數所需要的最小代價
int p[N], m;
int b_sum[N];
signed 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]), b_sum[i] = b_sum[i - 1] + b[i];
for(int i = 1;i <= n;i++)
scanf("%lld", &c[i]);
for(int i = 2;i <= n;i++)
a[i] = min(a[i - 1] + b[i], a[i]);
int q;
scanf("%lld", &q);
while(q --)
{
scanf("%lld", &m);
for(int i = 1;i <= m;i++)
{
scanf("%lld", &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] + b_sum[p[i] - 1] - b_sum[p[i - 1]]);
}
printf("%lld\n", min(g[m] + a[n], f[m] + b_sum[n] - b_sum[p[m]]));
}
return 0;
}