题解 | 购物单

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    N /= 10;

    vector<vector<int>> pr(m+1, vector<int>(3, 0));
    vector<vector<int>> prb(m+1, vector<int>(3, 0));

    for (int i = 1; i <= m; ++i) {
        int p, b, num;
        cin >> p >> b >> num;
        p /= 10; b *= p;
        if (num == 0) {
            pr[i][0] = p; prb[i][0] = b;
        } else {
            if (pr[num][1] == 0) {          // ✅ == 判断
                pr[num][1] = p;  prb[num][1] = b;  // ✅ = 赋值
            } else {
                pr[num][2] = p;  prb[num][2] = b;  // ✅ = 赋值
            }
        }
    }

    vector<vector<int>> dp(m+1, vector<int>(N+1, 0));
    for (int i = 1; i <= m; ++i) {
        int p1 = pr[i][0], b1 = prb[i][0];
        int p2 = pr[i][1], b2 = prb[i][1];
        int p3 = pr[i][2], b3 = prb[i][2];
        for (int j = 1; j <= N; ++j) {
            dp[i][j] = dp[i-1][j];  // ✅ 先继承上一行
            if (p1 > 0 && j >= p1)
                dp[i][j] = max(dp[i][j], dp[i-1][j-p1]+b1);
            if (p1 > 0 && p2 > 0 && j >= p1+p2)
                dp[i][j] = max(dp[i][j], dp[i-1][j-p1-p2]+b1+b2);
            if (p1 > 0 && p3 > 0 && j >= p1+p3)
                dp[i][j] = max(dp[i][j], dp[i-1][j-p1-p3]+b1+b3);
            if (p1 > 0 && p2 > 0 && p3 > 0 && j >= p1+p2+p3)
                dp[i][j] = max(dp[i][j], dp[i-1][j-p1-p2-p3]+b1+b2+b3);
        }
    }
    cout << dp[m][N] * 10 << endl;
}