Phrooce @ 2017-03-04 17:37:20
我的代码思路是把附件和主件看作同一物品 然后01背包 但是只有20分 数据测试时是正确的 求大神指导
一下是我的代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=32005,num=32000*2;
int n,m,w[num],zf[num],p[num],f[maxn],t=0,x,y,z,r=0;
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
w[++t]=x;
p[t]=x*y;
if(z==0)
{
zf[t]=++r;
}
else
{
t--;
int s=t;
for(int j=s;j>=1;j--)
{
if(zf[j]==z)
{
w[++t]=x+w[j];
p[t]=x*y+p[j];
zf[t]=zf[j];
}
}
}
}
for(int i=1;i<=t;i++)
{
for(int j=m;j>=w[i];j=j-10)
{
f[j]=max(f[j],f[j-w[i]]+p[i]);
}
}
printf("%d",f[m]);
return 0;
}