DP 求调
查看原帖
DP 求调
237650
Crouy_Li_Dorac楼主2024/8/13 11:33

95,最后一个点过不去

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=5e5+10;
int n,q,m;
int a[N],b[N],c[N],d[N],p[N],cpre[N],bpre[N],dp[N];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)	scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)	scanf("%d",&c[i]);
	for(int i=1;i<=n;i++){
		d[i]=min(d[i-1]+b[i],a[i]);
		bpre[i]=bpre[i-1]+b[i];
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%d",&p[i]);
			cpre[i]=cpre[i-1]+c[p[i]];
		}
		dp[1]=min(d[p[1]]+cpre[1],d[p[1]-1]);
		for(int i=2;i<=m;i++){
			
			dp[i]=min(d[p[i]]+cpre[i],d[p[i]-1]+cpre[i-1]);
			dp[i]=min(dp[i],dp[i-1]+bpre[p[i]-1]-bpre[p[i-1]]);
		}
		printf("%d\n",min(d[n]+cpre[m],dp[m]+bpre[n]-bpre[p[m]]));
	}
} 
2024/8/13 11:33
加载中...