题解 | #密码验证合格程序#

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

#define MAX(a, b) ((a > b) ? (a) : (b))
static int satisfied[2][3201] = {0};
static int satPrice[60][4][2] = {0}; /* 60 个物品，4 种是否带对应附件情况，最后的 2 分别对应物品价格及满意度 */
int main(int argc, char** argv)
{
    int N, m; /* 输入最大价格 N，物品个数 m */
    scanf("%d%d", &N, &m); N /= 10; /* 价格为 10 的倍数，下面计价都除以 10 使用连续的自然数 */
    int v, p, q; /* 与题目价格、重要度、附件标号对应 */
    for (int i = 0; i < m; i++) { /* 循环接收输入数据 */
        scanf("%d%d%d", &v, &p, &q); v /= 10; /* 价格是 10 的整数倍，除以十可以按顺序编号，对应统计满意度下标 */
        if (q == 0) { /* 当前物品为主件 */
            satPrice[i][0][0] = v; /* 存放仅主件情况下的价格 */
            satPrice[i][0][1] = v * p; /* 存放仅主件情况下的满意度 */
        } else if (satPrice[q - 1][1][0] == 0) { /* q - 1 主件对应的附件不存在时，先填充附件1信息 */
            satPrice[q - 1][1][0] = v; /* 附件1对应的价格 */
            satPrice[q - 1][1][1] = v * p; /* 附件1对应的满意度 */
        } else { /* 当前因为最大只有两个附件，因此附件1被统计后，附件2信息上来时，可以直接统计附件2及与1组合的情况 */
            satPrice[q - 1][2][0] = v;  /* 附件2对应的价格 */
            satPrice[q - 1][2][1] = v * p;  /* 附件2对应的满意度 */
            satPrice[q - 1][3][0] = satPrice[q - 1][1][0] + v;  /* 附件1 和 2组合对应的价格 */
            satPrice[q - 1][3][1] = satPrice[q - 1][1][1] + v * p; /* 附件1 和 2组合对应的满意度 */
        }
    }

    for (int i = 0; i < m; i++) { /* 循环给附件添加主件的价格和满意度 */
        for (int j = 1; j < 4; j++) {
            if (satPrice[i][j][0] != 0) { /* 将输入统计的所有非 0 附件都加上其主件对应的价格和满意度 */
                satPrice[i][j][0] += satPrice[i][0][0]; /* 非 0 附件价格加上主件价格 */
                satPrice[i][j][1] += satPrice[i][0][1]; /* 非 0 附件满意度加上主件满意度 */
            }
        }
    }

    for (int i = 0; i < m; i++) { /* 循环取满意度最大值 */
        memcpy(satisfied[0], satisfied[1], sizeof(satisfied[1])); /* 保留上一轮取的值 */
        memset(satisfied[1], 0, sizeof(satisfied[1])); /* 清空本轮待重新统计的值 */
        for (int j = 1; j <= N; j++) {
            int maxVal = satisfied[0][j];
            for (int k = 0; k < 4; k++) {
                if (j >= satPrice[i][k][0]) {
                    maxVal = MAX(maxVal, satisfied[0][j - satPrice[i][k][0]] + satPrice[i][k][1]);
                }
            }
            satisfied[1][j] = maxVal;
        }
    }

    printf("%d\n", satisfied[1][N] * 10);
    return 0;
}