蒟蒻求助
查看原帖
蒟蒻求助
159959
虫洞吞噬者楼主2021/10/24 09:15

rt,二进制优化后反而WA?????

求大佬指正

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,maxn,ans=inf,cnt;
int sum[100100],cos[100100],coss[100100],val[100100];
int f1[100100],f2[100100];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&coss[i]),maxn=max(maxn,coss[i]);
	for(int i=1;i<=n;++i)
	{
		int b;
		scanf("%d",&b);
		int bas=1;
		while(b>=bas)
		{
			b-=bas;
			cos[++cnt]=coss[i]*bas;
			val[cnt]=bas;
			bas*=2;
		}
		if(b)
		{
			cos[++cnt]=coss[i]*b;
			val[cnt]=b;
			b=0;
		}
	}
	memset(f1,0x3f,sizeof(f1));
	memset(f2,0x3f,sizeof(f2));
	f1[0]=f2[0]=0;
	int top=m+maxn*maxn;
	for(int i=1;i<=n;++i)
		for(register int j=cos[i];j<=top;++j)f2[j]=min(f2[j],f2[j-cos[i]]+1);
	n=cnt;
	for(int i=1;i<=n;++i)
		for(register int j=top;j>=cos[i];--j)f1[j]=min(f1[j],f1[j-cos[i]]+val[i]);
	for(int i=m;i<=top;++i)ans=min(ans,f1[i]+f2[i-m]);
	ans=min(ans,f1[m]);
	if(ans==inf)printf("-1");
	else printf("%d",ans);
	return 0;
}
2021/10/24 09:15
加载中...