许豪 @ 2017-04-15 18:36:27
#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int jian[61][61]={0};
int tui2[10001]={0};
int tui[61][61]={0};
int x,y;
int c[61],v[61];
int maxl(int,int);
int main()
{
cin>>n>>m;
for(int j=1;j<=m;j++)
{
cin>>v[j]>>x;
cin>>y;
if(y!=0) jian[y][++jian[y][0]]=j;
c[j]=x*v[j];
}
for(int s=1;s<=m;s++)
{
for(int d=1;d<=jian[s][0];d++)
{
for(int sd=n-v[s];sd>=v[jian[s][d]];sd--)
{
tui[s][sd]=maxl(tui[s][sd],tui[s][sd-v[jian[s][d]]]+c[jian[s][d]]);
}
}
}
for(int sa=1;sa<=m;sa++)
{
for(int j=1;j<=n-v[sa];j++)
{
tui[sa][j]+=c[sa];
}
}
for(int f=1;f<=m;f++)
{
for(int k=n;k>=v[f];k--)
{
for(int ss=1;ss<=k;ss++)
{
tui2[k]=maxl(tui2[k],tui2[k-ss-v[f]]+tui[f][ss]);
}
}
}
cout<<tui2[n];
return 0;
}
int maxl(int xx,int yy)
{
if(xx>yy) return xx;
else return yy;
}