题解 | #购物单#

#include <stdio.h>

typedef struct{
    int v,p;
    int f1,f2;
    int flag;
}node;

int max(int a,int b){
    if(a>b)return a;
    else return b;
}

int main() {
    int n,m,v,p,q;
    int i,j;
    int dp[60][32000];
    node goods[60];
    for(i=0;i<60;i++){
        goods[i].f1=-1;
        goods[i].f2=-1;
        goods[i].flag=0;
    }
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&v,&p,&q);
        goods[i].v=v;
        goods[i].p=v*p;
        if(q==0){
            goods[i].flag=1;
        }
        else{
            if(goods[q-1].f1==-1){
                goods[q-1].f1=i;
            }
            else{
                goods[q-1].f2=i;
            }
        }
    }
    for(i=1;i<=m;i++){
        for(j=0;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            if(goods[i-1].flag==0){
                continue;
            }
            if(j>=goods[i-1].v){
                dp[i][j]=max(dp[i][j],dp[i-1][j-goods[i-1].v]+goods[i-1].p);
            }
            if(goods[i-1].f1!=-1&&j>=goods[i-1].v+goods[goods[i-1].f1].v){
                dp[i][j]=max(dp[i][j],dp[i-1][j-goods[i-1].v-goods[goods[i-1].f1].v]+goods[i-1].p+goods[goods[i-1].f1].p);
            }
            if(goods[i-1].f2!=-1&&j>=goods[i-1].v+goods[goods[i-1].f2].v){
                dp[i][j]=max(dp[i][j],dp[i-1][j-goods[i-1].v-goods[goods[i-1].f2].v]+goods[i-1].p+goods[goods[i-1].f2].p);
            }
            if(goods[i-1].f1!=-1&&goods[i-1].f2!=-1&&j>=goods[i-1].v+goods[goods[i-1].f1].v+goods[goods[i-1].f2].v){
                dp[i][j]=max(dp[i][j],dp[i-1][j-goods[i-1].v-goods[goods[i-1].f1].v-goods[goods[i-1].f2].v]+goods[i-1].p+goods[goods[i-1].f1].p+goods[goods[i-1].f2].p);
            }
        }
    }
    printf("%d",dp[m][n]);
    return 0;
}