题解 | #购物单#

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    N /= 10; //缩小后续dp空间（N不是10的整倍数也无妨，省去多出来的余数不影响，因为物品质量全是10的整倍数）
    vector<vector<int>> w(m + 1, vector<int>(3, 0)); //质量(1主件2附件)
    vector<vector<int>> v(m + 1, vector<int>(3, 0)); //价值
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10;
        b *= a;
        if (c == 0) {
            w[i][0] = a;
            v[i][0] = b;
        } else {
            if (w[c][1] == 0) {
                w[c][1] = a;
                v[c][1] = b;
            } else {
                w[c][2] = a; //此处只能保存该附件值，而无法直接求出主件+附件，因为添加附件时主件可能还未添加
                v[c][2] = b;
            }
        }
    }
    //分组背包
    vector<int> dp(N + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = N; j >= w[i][0]; j--) {
            int p0 = dp[j - w[i][0]] + v[i][0];
            int p1 = j - w[i][0] - w[i][1] >= 0 ? dp[j - w[i][0] - w[i][1]] + v[i][0] + v[i][1] : 0;
            int p2 = j - w[i][0] - w[i][2] >= 0 ? dp[j - w[i][0] - w[i][2]] + v[i][0] + v[i][2] : 0;
            int p3 = j - w[i][0] - w[i][1] - w[i][2] >= 0 ?
                     dp[j - w[i][0] - w[i][1] - w[i][2]] + v[i][0] + v[i][1] + v[i][2] : 0;
            dp[j] = max({dp[j], p0, p1, p2, p3}); //不取/取四种情况里的某一种
        }
    }
    cout << dp.back() * 10;
}