题解 | #购物单#

#include <math.h>
#include <stdio.h>
#include <string.h>

int main() {
    int N, m;
    scanf("%d %d",&N,&m);
    int v,t,o;
        int we[60][4] = {0};
    int pr[60][4] = {0};
    for (int i = 0; i<m; i++) {
    scanf("%d %d %d\n",&v,&t,&o);
    if (o == 0) {
    
    we[i][0] = v*t;                 //主体计算
    pr[i][0] = v;
    }
    else if (pr[o-1][1] == 0) {     //第一个附件计算
        we[o-1][1] = v*t;
        pr[o-1][1] = v;
    } else {
        we[o-1][2] = v*t;           //第二个附件计算
        pr[o-1][2] = v;
        we[o-1][3] = v*t + we[o-1][1];//两个个附件一起计算
        pr[o-1][3] = v + pr[o-1][1];
    }  
    }


for (int i = 0; i<m;i++) {
    if (pr[i][0] != 0 || pr[i][1] == 0){
        for (int j = 1; j<4; j++) {
            we[i][j] += we[i][0];       //在附件位置上加主体的值方便后续计算
            pr[i][j] += pr[i][0];
        }
    }
}

int dp[N+1];//开始动态规划，先设置一维数组
memset(dp, 0, sizeof(dp));//数组初始化为0
for (int i = 0; i<m; i++) {
    if (pr[i][0] == 0) continue;//附件不能单独买
    for (int j = N; j>0; j -= 10) {
        for (int k = 0; k<4; k++) {
            if (j >= pr[i][k]) {    //剩余的钱能买下这个设备
                dp[j] = fmax(dp[j], we[i][k]+dp[j-pr[i][k]]);//看时不买的满意度大还是买了的满意度大
            }
        }
    }
}


printf("%d",dp[N]);
    return 0;
}