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;
}