DP 50分求助
查看原帖
DP 50分求助
999274
CNS_5t0_0r2楼主2023/10/18 21:10
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 9;
int n,q,m;
int a[N],b[N],c[N];
int s_a[N],s_b[N],s_c[N];
int p[N],s_p[N];
int read() {
	char c = getchar();
	int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}
int dp[N],dp2[N];
signed main(){
	n = read();
	for(int i = 1;i <= n;i++){
		a[i] = read();
		s_a[i] = s_a[i - 1] + a[i];
	}
	for(int i = 1;i <= n;i++){
		b[i] = read();
		s_b[i] = s_b[i - 1] + b[i];
	}
	for(int i = 1;i <= n;i++){
		c[i] = read();
		s_c[i] = s_c[i - 1] + c[i];
	}
	for(int i = 1;i <= n;i++)
		dp2[i] = min(dp2[i - 1] + b[i],min(a[i],s_b[i]));
	q = read();
	for(;q;q--){
		m = read();
		for(int i = 1;i <= m;i++){
			p[i] = read();
			s_p[i] = s_p[i - 1] + c[p[i]];
		}
		if(!m){
			int ans = dp2[n];
//			for(int i = 0;i <= n;i++)
//				ans = min(ans,a[i] + s_b[n] - s_b[i]);
			printf("%lld\n",ans);
			continue;
		}
		dp[1] = min(dp2[p[1] - 1],min(min(a[p[1] - 1],s_b[p[1] - 1]),a[p[1]] + c[p[1]]));
		for(int i = 2;i <= m;i++){
			if(p[i] == p[i - 1] + 1)
				dp[i] = min(dp[i - 1],min(a[p[i] - 1] + s_p[i - 1],a[p[i]] + s_p[i]));
			else
				dp[i] = min(dp[i - 1] + s_b[p[i] - 1] - s_b[p[i - 1]],min(a[p[i] - 1] + s_p[i - 1],a[p[i]] + s_p[i]));
		}
		printf("%lld\n",min(dp[m] + s_b[n] - s_b[p[m]],dp2[n] + s_p[m]));
	}
	return 0;
}
2023/10/18 21:10
加载中...