最后一个没有分的点WA了
查看原帖
最后一个没有分的点WA了
159959
虫洞吞噬者楼主2021/9/22 17:47

RT,求大佬帮忙查错

思路:对于正常物品进行多重背包并二进制优化,对于奇货进行完全背包,然后因为不会写读入输出优化于是吸氧了,结果最后一个点挂了(可能是另外的一组hack数据)

附:代码

	#include<cstdio>
	#include<cstring>
	#include<algorithm>
	using namespace std;
	int n,m,v,ans=-1,cnt;
	int cos[100100],val[100100],a[100100],b[100100],c[100100];
	int f[100100];
	int main()
	{
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=n;++i)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			int bas=1;
			while(z)
			{
				++cnt;
				if(z>=bas)
				{
					z-=bas;
					val[cnt]=y*bas;
					cos[cnt]=x*bas;
				}
				else
				{
					val[cnt]=y*z;
					cos[cnt]=x*z;
					z=0;
				}
				bas*=2;
			}
		}
		for(int i=1;i<=m;++i)scanf("%d%d%d",&a[i],&b[i],&c[i]);
		for(int i=1;i<=cnt;++i)
			for(register int j=v;j>=cos[i];--j)f[j]=max(f[j],f[j-cos[i]]+val[i]);
		for(int i=1;i<=m;++i)
			for(register int j=v;j>=0;--j)
				for(register int k=0;k<=j;++k)
				{
					int cur=a[i]*k*k+b[i]*k+c[i];
					f[j]=max(f[j],f[j-k]+cur);
				}
		printf("%d",f[v]);
		return 0;
	}
2021/9/22 17:47
加载中...