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

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int    N,n,v[61],m[61],p[61],link[61][3],d[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;
    }
    for(int i=1;i<=n;i++)
    for(int j=N;j>=1;j--)
    if(p[i]==0 && j >= v[i]){
          d[j]=max(d[j],d[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])
            d[j]=max(d[j],d[j-v[i]-v[a]]+v[i]*m[i]+v[a]*m[a]);
          if(link[i][0]==2){
                if(j>=v[i]+v[b])
                    d[j]=max(d[j],d[j-v[i]-v[b]]+v[i]*m[i]+v[b]*m[b]);
                if(j>=v[i]+v[a]+v[b])
                    d[j]=max(d[j],d[j-v[i]-v[a]-v[b]]+v[i]*m[i]+v[a]*m[a]+v[b]*m[b]);
          }
    }
    cout << d[N]*10<< endl;
    return 0;
}

解题思路:





注意事项:





参考代码: