分享一个贪心做法
查看原帖
分享一个贪心做法
739552
mygr楼主2023/10/16 10:58

?可能是错解
求大佬hack

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=5e5+5,inf=0x7fffffffffffffff;
int n,m,q,a[Max],b[Max],c[Max];
int in[Max],tb[Max],tot[Max],tc[Max];
inline int read()
{
	char c;
	int a=0;
	c=getchar();
	while(c<'0' or '9'<c)c=getchar();
	while('0'<=c and c<='9')
	{
		a=a*10+c-'0';
		c=getchar();
	}
	return a;
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=n;i>=1;i--)
		tb[i]=tb[i+1]+b[i];
	for(int i=1;i<=n;i++)
		a[i]=min(a[i],a[i-1]+b[i]);
	scanf("%d",&q);
	int ans;
	while(q--)
	{
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			in[i]=read();
			tc[i]=tc[i-1]+c[in[i]];
		}
		tot[m+1]=0;
		for(int i=m;i>=1;i--)tot[i]=tot[i+1]+b[in[i]];
		
		ans=a[n]+tc[m];
		for(int i=1;i<=m;i++)
		{
			ans=min(ans,a[in[i]-1]+tc[i-1]+tb[in[i]+1]-tot[i+1]);
			ans=min(ans,a[in[i]]+tc[i]+tb[in[i]+1]-tot[i+1]);
		}
		printf("%lld\n",ans);
	}
}
2023/10/16 10:58
加载中...