//大牛幫幫忙！！！

#include<iostream>
using namespace std;
int c[61],w[61];//原始c、w
int kids[61][2],father[61];//主附件關系
int lc[61][4],lw[61][4];//分組后c、w
int f[3201];
int n,m,fa=0;
void init(){
int k[61];
cin>>n>>m;
for(int i=1;i<=m;i++){cin>>c[i]>>w[i]>>k[i];c[i]/=10;w[i]*=c[i];}
for(int i=1;i<=m;i++){if(!k[i]){fa++;father[fa]=i;}}
for(int i=1;i<=m;i++){
if(k[i]){
if(kids[k[i]][0]){kids[k[i]][1]=i;}
else{kids[k[i]][0]=i;}
}
}
for(int i=1;i<=fa;i++){
cout<<kids[i][0]<<" "<<kids[i][1]<<" "<<father[i]<<endl;
}
}
void make_club(){
for(int i=1;i<=fa;i++){
lc[i][0]=c[father[i]];lw[i][0]=w[father[i]];
lc[i][1]=lc[i][0]+c[kids[i][0]];lw[i][1]=lw[i][0]+w[kids[i][0]];
lc[i][2]=lc[i][0]+c[kids[i][1]];lw[i][2]=lw[i][0]+w[kids[i][1]];
lc[i][3]=lc[i][1]+lc[i][2]-lc[i][0];lw[i][3]=lw[i][1]+lw[i][2]-lw[i][0];
}
for(int i=1;i<=fa;i++){
for(int j=0;j<=3;j++){
cout<<lc[i][j]<<" "<<lw[i][j]<<endl;
}
cout<<endl;
}
}
void dp(){
for(int k=1;k<=fa;k++){
for(int v=(n/10);v>=0;v--){
//for(int v=0;v<=(n/10);v++){
for(int i=0;i<=3;i++){
if(v-lc[k][i]>=0){f[v]=max(f[v],f[v-lc[k][i]]+lw[k][i]);}
}
}
for(int v=0;v<=n/10;v++){cout<<f[v]<<" ";}
cout<<endl;
}
cout<<f[n/10]*10;
}
int main(){
//freopen("budget.in" ,"r",stdin );
//freopen("budget.out","w",stdout);
init();
make_club();
dp();
system("pause");
return 0;
}
/*
自測60分
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
正確答案為7340，我的答案為7200。中間加了幾句調試，答案是最后一行；
大牛們幫幫忙！！！
  回復  更多評論