90分 求解

#include <stdio.h>
int price[65],import[65],dp[33000],fs[65][3],zj[65],n,m,t,x;
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",price+i,import+i,&t);
        if(t)fs[t][++fs[t][0]]=i;else zj[x++]=i;
    }
    for(int i=0;i<x;i++){
        int k=zj[i];
        for(int j=n;j>=price[k];j--){
            dp[j]=max(dp[j],dp[j-price[k]]+price[k]*import[k]);
            if(fs[k][0]==1&&j>=price[k]+price[fs[k][1]])
                dp[j]=max(dp[j],dp[j-price[k]-price[fs[k][1]]]+price[k]*import[k]+price[fs[k][1]]*import[fs[k][1]]);
            if(fs[k][0]==2){
                if(j>=price[k]+price[fs[k][2]])
                    dp[j]=max(dp[j],dp[j-price[k]-price[fs[k][2]]]+price[k]*import[k]+price[fs[k][2]]*import[fs[k][2]]);
                if(j>=price[k]+price[fs[k][1]]+price[fs[k][2]])
                    dp[j]=max(dp[j],dp[j-price[k]-price[fs[k][1]]-price[fs[k][2]]]+price[k]*import[k]+price[fs[k][1]]*import[fs[k][1]]+price[fs[k][2]]*import[fs[k][2]]);
            }
        }
    }
    printf("%d",dp[n]);
    return 0;
}