0tps求调
查看原帖
0tps求调
801226
Heart_Beating楼主2023/10/17 19:31
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
long long a[1000000],b[1000000],c[1000000];
long long sum[1000000];//cnt1记录从0改1的代价
long long cnt[1000000];
long long dp[1000000],Inf=1000000000000000000;
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(register int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	for(register int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		sum[i]=sum[i-1]+c[i];
	}
	cin>>q;
	while(q--)
	{
		cin>>m;
		memset(cnt,0,sizeof(cnt));
		memset(dp,Inf,sizeof(dp));
		dp[0]=0;
		map<int,bool> vis;
		int temp;
		for(register int i=1;i<=m;i++)
		{
			cin>>temp;
			vis[temp]=true;
		}
		for(register int i=1;i<=n;i++)
		{
			if(vis[i])
			{
				//cout<<"orz\n";
				cnt[i]=cnt[i-1];
			}
			else
			{
				cnt[i]=cnt[i-1]+c[i];
			}
		}
//		for(register int i=1;i<=n;i++)
//		{
//			printf("%d %d\n",sum[i],cnt[i]);
//		}
		for(register int i=1;i<=n;i++)
		{
			if(vis[i])
			{
				dp[i]=min(dp[i-1],a[i]+sum[i]-cnt[i]);
			}
			else
			{
				dp[i]=min(dp[i-1]+b[i],a[i]+sum[i]-cnt[i]);
				//cout<<i<<' '<<dp[i-1]+b[i]<<' '<<a[i]+sum[i]-cnt[i]<<endl; 
			}
			//printf("%d\n",dp[i]);
			//printf("%d\n",a[4]+sum[4]-cnt[4]);
		}
		printf("%d\n",dp[n]);
	}
	return 0;
}
2023/10/17 19:31
加载中...