题解 | #购物单#

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

int main() {
    int N, m;
    cin >> N >> m;
    N /= 10;    // 价格是10的倍数
    // 两个数组存储每个商品的价格和重要度
    vector<vector<int>> price(m+1, vector<int>(3, 0));  //  [主][附1][附2]
    vector<vector<int>> value(m+1, vector<int>(3, 0));
    
    // 动态规划dp[i][j]:i为物品位置，总价格不超过j的最大满意度
    vector<vector<int>> dp(m+1, vector<int>(N+1, 0));   
    for(int i=1; i<=m; ++i) {
        int v, p, q;
        cin >> v >> p >> q;
        if(q == 0) {
            // 主件
            price[i][0] = v/10;
            value[i][0] = p;
        }
        else {
            if(value[q][1] == 0) {  // 第一个附件
                price[q][1] = v/10;
                value[q][1] = p;
            }
            else {                  // 第二个附件
                price[q][2] = v/10;
                value[q][2] = p;
            }
        }
    }

    for(int i=1; i<=m; ++i) {
        int price1 = price[i][0], value1 = value[i][0];
        int price2 = price[i][1], value2 = value[i][1];
        int price3 = price[i][2], value3 = value[i][2];
        for(int j=1; j<=N; ++j) {
            dp[i][j] = j >= price1 ? max(dp[i-1][j-price1] + price1*value1, dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= price1+price2 ? max(dp[i-1][j-price1-price2] + price1*value1 + price2*value2, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= price1+price3 ? max(dp[i-1][j-price1-price3] + price1*value1 + price3*value3, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= price1+price2+price3 ? max(dp[i-1][j-price1-price2-price3] + price1*value1 + price2*value2 + price3*value3, dp[i][j]) : dp[i][j];
        }
    }

    cout << dp[m][N]*10;

    return 0;
}
// 64 位输出请用 printf("%lld")

注意动态规划递推公式