测试点 @ 2018-04-20 23:26:52
#include<stdio.h>
#include<string.h>
int n,m,v[65][65],w[65][65],f[32005];
int main()
{
memset(f,0,sizeof(f));
memset(v,0,sizeof(v));
memset(w,0,sizeof(w));
scanf("%d%d",&n,&m);
int i,j,z,a,b,c,sum=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c==0)
{
sum++;
w[sum][1]=b*a;v[sum][1]=a;
}
else
{
j=2;
for(;j<=65;j++)
{
if(w[c][j]==0) break;
}
w[c][j]=b*a;v[c][j]=a;
}
}
for(z=1;z<=sum;z++)
{
for(i=n;i>=v[z][1];i--)
{
if(f[i-v[z][1]]+w[z][1]>f[i]) f[i]=f[i-v[z][1]]+w[z][1];
if(i>=v[z][1]+v[z][2]&&f[i-v[z][1]-v[z][2]]+w[z][1]+w[z][2]>f[i]) f[i]=f[i-v[z][1]-v[z][2]]+w[z][1]+w[z][2];
if(i>=v[z][1]+v[z][3]&&f[i-v[z][1]-v[z][3]]+w[z][1]+w[z][3]>f[i]) f[i]=f[i-v[z][1]-v[z][3]]+w[z][1]+w[z][3];
if(i>=v[z][1]+v[z][2]+v[z][3]&&f[i-v[z][1]-v[z][2]-v[z][3]]+w[z][1]+w[z][2]+w[z][3]>f[i]) f[i]=f[i-v[z][1]-v[z][2]-v[z][3]]+w[z][1]+w[z][2]+w[z][3];
}
}
printf("%d",f[n]);
return 0;
}