C 解法, 执行用时: 1ms, 内存消耗: 420KB, 提交时间: 2021-09-12

#include <stdio.h>
#define Max(x,y) (x>y?x:y)
int main(void)
{
    int N, m;
    scanf("%d %d", &N, &m);
    int val[m+1][3];
    int wei[m+1][3];
    memset(val, 0, 3*(m+1)*sizeof(int));
    memset(wei, 0, 3*(m+1)*sizeof(int));
    //init
    for(int i = 1; i <= m; i++) {
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if(!q) {//主
            val[i][0] = v/10;
            wei[i][0] = v*p/10;
        } else if(val[q][1] == 0) {//附1
            val[q][1] = v/10;
            wei[q][1] = v*p/10;
        } else {//附2
            val[q][2] = v/10;
            wei[q][2] = v*p/10;
        }
    }
    /*
    for(int i = 1; i <= m; i++) {
        printf("%d-%d-%d;", i, val[i][0], wei[i][0]);
        printf("%d-%d;", val[i][1], wei[i][1]);
        printf("%d-%d;\n", val[i][2], wei[i][2]);
    }*/
    //dp
    int dp[3200] = {0};
    for(int i = 1; i <= m; i++) {
        for(int j = N/10; j >= 0; j--) {
            if(val[i][0] <= j) {
                dp[j] = Max(dp[j], wei[i][0] + dp[j - val[i][0]]);
            }
            if(val[i][1] && (val[i][0] + val[i][1]) <= j) {
                dp[j] = Max(dp[j], 
                            wei[i][0] + wei[i][1] 
                            + dp[j - val[i][0] - val[i][1]]);
            }
            if(val[i][2] && (val[i][0] + val[i][2]) <= j) {
                dp[j] = Max(dp[j], 
                            wei[i][0] + wei[i][2] 
                            + dp[j - val[i][0] - val[i][2]]);
            }
            if(val[i][2] && (val[i][0] + val[i][1] + val[i][2]) <= j) {
                dp[j] = Max(dp[j], 
                            wei[i][0] + wei[i][1] + wei[i][2]  
                            + dp[j - val[i][0] - val[i][1] - val[i][2]]);
            }
        }
    }
    printf("%d", dp[N/10]*10);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 288KB, 提交时间: 2021-09-22

#include<stdio.h>
#include <stdlib.h>
#define max(a,b) (a>b?a:b)
int V[61][3];
int VP[61][3];
int DP[3200];
int main()
{
    int N,m,v,p,q;
    
    while(scanf("%d%d",&N,&m)!=EOF)
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&v,&p,&q);
            if(q)
            {
                if(V[q][1])
                {
                    V[q][2]=v/10;
                    VP[q][2]=v*p;
                }
                else
                {
                    V[q][1]=v/10;
                    VP[q][1]=v*p;
                }
            }
            else
            {
                V[i][0]=v/10;
                VP[i][0]=v*p;
            }
        }
        int vpt=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=N/10;j>=V[i][0]&&V[i][0]!=0;j--)
            {
                 //情况1，只有主（默认情况）
                vpt=V[i][0];
                DP[j]=max(DP[j],DP[j-vpt]+VP[i][0]);
                //情况2，有附件1+主（附件2有没有不管）
                if(V[i][1]!=0)
                {
                    vpt=V[i][0]+V[i][1];
                    if(j>=vpt)
                    {
                        DP[j]=max(DP[j],DP[j-vpt]+VP[i][0]+VP[i][1]);
                    }
                }
                 
                if(V[i][2]!=0)
                {
                    //情况3，附件2+主
                    vpt=V[i][0]+V[i][2];
                    if(j>=vpt)
                    {
                        DP[j]=max(DP[j],DP[j-vpt]+VP[i][0]+VP[i][2]);
                    }
                    //情况4，附件1+附件2+主
                    vpt=V[i][0]+V[i][2]+V[i][1];
                    if(j>=vpt)
                    {
                        DP[j]=max(DP[j],DP[j-vpt]+VP[i][0]+VP[i][2]+VP[i][1]);
                    }
                }
                
            }
        }
        printf("%d",DP[N/10]);
    }
    return 0;
}