【金明的预算方案】 （C++代码）

#include<iostream>
#include<cstring>
using namespace std;
int    N,n,v[61],m[61],p[61],link[61][3],f[61][3200];
int main(void){
    cin >> N >> n ;
    N/=10;
    for(int i=1;i<=n;i++){
        cin >> v[i] >> m[i] >> p[i];
        v[i]/=10;
        if(p[i]) link[p[i]][++link[p[i]][0]]=i;
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=N;j++)
    {
         f[i][j]=(i==1?0:f[i-1][j]);//这里有一个巨大的坑，哈哈哈
         if(p[i]==0 && j >=v[i]){
             f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*m[i]);
             int  a = link[i][1], b = link[i][2];
             if(link[i][0] && j>=v[i]+v[a]) f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[a]]+v[i]*m[i]+v[a]*m[a]);
             if(link[i][0]==2){
                if(j>=v[i]+v[b]) f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[b]]+v[i]*m[i]+v[b]*m[b]);
                if(j>=v[i]+v[a]+v[b]) f[i][j]=max(f[i][j],f[i-1][j-v[i]-v[a]-v[b]]+v[i]*m[i]+v[a]*m[a]+v[b]*m[b]);
             }
        }
    }
    cout << f[n][N]*10<< endl;
    return 0;
}