题解 | 购物单

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

void getGoods(int count, vector< vector<int>>& goods) {
    for (int i = 1; i < count; i++) {   // 接收数据
        // goods[i][0] 为 价格 goods[i][1] 为 重要度 goods[i][2] 为 主件编号
        cin >> goods[i][0] >> goods[i][1] >> goods[i][2];
        goods[i][0] /= 10;
    }
    for (int i = 1; i < count; i++) {
        if (goods[i][2] != 0) { // 如果为附件 goods[i][3] 为编号为i的商品第一个附件
            if (goods[goods[i][2]][3] == 0) {
                // goods[i][3] 为编号为i的商品第一个附件
                goods[goods[i][2]][3] = i;
            } else if (goods[goods[i][2]][4] == 0) {
                // goods[i][4] 为编号为i的商品第二个附件
                goods[goods[i][2]][4] = i;
            }
        }
    }
}
/*
i 为 物品的编号 j 为 预算 dp[i][j] 为j 预算下 买 前i 件物品的 最佳满意度
可以将问题抽象为 dp[i][j] = max{dp[i-1][j], judge(i, j)}
其中 judge(i, j)表示 dp[i][j]在以下四种情况的满意度
1、只买 i 本身， 无附件
2、买 i本身 加 i的第一个附件
3、买i本身 加 i 的第二个附件
4、买i本身加 i 的两个附件
*/

int max(int a, int b, int c, int d){
    return max({a, b, c, d});
}

void maxSatisfaction(int money, int count, vector< vector<int>>& goods) {
    vector < vector<int>> dp(count + 1, vector(money + 1, 0));
    for (int i = 0; i < count + 1; i++) {
        int price0, price1, price2, price3;
        int value0, value1, value2, value3;
        price0 = price1 = price2 = price3 = 0;
        value0 = value1 = value2 = value3 = 0;

        // 只考虑主件
        price0 = goods[i][0];
        value0 = goods[i][1] * goods[i][0];
        // 主件+附件1
        price1 = goods[goods[i][3]][0] + price0;
        value1 = goods[goods[i][3]][1] * goods[goods[i][3]][0] + value0;
        // 主件+附件2
        price2 = goods[goods[i][4]][0] + price0;
        value2 = goods[goods[i][4]][1] * goods[goods[i][4]][0] + value0;
        // 主件+附件1+附件2
        price3 = price1 + price2 - price0;
        value3 = value1 + value2 - value0;

        // 填充dp 数组
        for (int j = 1; j < money + 1; j++) {
            if (goods[i][2] != 0 || j < price0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                int a0, a1, a2, a3;
                a0 = a1 = a2 = a3 = 0;
                // 只买主件
                if (j >= price0 && price0 != 0) {
                    a0 = max(dp[i - 1][j], dp[i - 1][j - price0] + value0);
                }
                // 主件 + 附件1
                if (j >= price1 && price1 != 0) {
                    a1 = max(dp[i - 1][j], dp[i - 1][j - price1] + value1);
                }
                // 主件 + 附件2
                if (j >= price2 && price2 != 0) {
                    a2 = max(dp[i - 1][j], dp[i - 1][j - price2] + value2);
                }
                // 主件 + 附件1 + 附件2
                if (j >= price3 && price3 != 0) {
                    a3 = max(dp[i - 1][j], dp[i - 1][j - price3] + value3);
                }
                dp[i][j] = max(a0, a1, a2, a3);
            }  
        }
    }

    cout << dp[count][money] * 10 << endl;
}

int main() {

    int money, count;
    cin  >> money >> count;
    money /= 10;
    vector< vector<int>> goods(count +1, vector<int>(5, 0));   // goods每行有五列
    getGoods(count +1 , goods);
    maxSatisfaction(money, count, goods);

    return 0;

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