题解 | #购物单#

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    vector<vector<int>> subjects(m, vector<int>(3));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < 3; j++)
            cin >> subjects[i][j];
    map<int, vector<vector<int>>> zhujianMap;
    int zhujianNum = 0;
    for (int i = 0; i < m; i++) {
        if (subjects[i][2] == 0) { //主件
            vector<vector<int>> temp;
            vector<int> zhujianInfo;
            zhujianInfo.push_back(subjects[i][0]);
            zhujianInfo.push_back(subjects[i][1]);
            temp.push_back(zhujianInfo);
            zhujianMap[i + 1] = temp;
            zhujianNum++;
        } else {
            ;
        }
    }
  //先把主件塞进map里，再把附件添加到map中主件对应的数组里。
 //bug1：之前if-else写在一个循环里，导致先出现附件的话，找不到对应主件，附件就添加不上
    for (int i = 0; i < m; i++) {
        if (subjects[i][2] == 0) { //主件
            ;
        } else {
            int zhujianID = subjects[i][2];
            vector<vector<int>> temp = zhujianMap[zhujianID];
            vector<int> fujianInfo;
            fujianInfo.push_back(subjects[i][0]);
            fujianInfo.push_back(subjects[i][1]);
            temp.push_back(fujianInfo);
            zhujianMap[zhujianID] = temp;
        }
    }

    vector<vector<int> > w(zhujianNum + 1, vector<int>(4)); //物品价格
    vector<vector<int> > v(zhujianNum + 1, vector<int>(4)); //物品价值
    //k-四种情况：主件，主件+附件1，主件+附件2，主件+附件1+附件2
    int zhujianID = 1;
    //计算每个主件（及其附件）的四种情况的价值和价格
    for (auto it : zhujianMap) {
        int key = it.first;
        vector<vector<int>> value = it.second;
        if (value.size() == 1) { //此主件无附件
            for (int k = 0; k < 4; k++) {
                w[zhujianID][k] = value[0][0];
                v[zhujianID][k] = value[0][0] * value[0][1];
            }
        } else if (value.size() == 2) { //此主件有1个附件
            w[zhujianID][0] = value[0][0];
            v[zhujianID][0] = value[0][0] * value[0][1];
            w[zhujianID][1] = value[0][0] + value[1][0];
            v[zhujianID][1] = value[0][0] * value[0][1] + value[1][0] * value[1][1];

            w[zhujianID][2] = value[0][0];
            v[zhujianID][2] = value[0][0] * value[0][1];
            w[zhujianID][3] = value[0][0] + value[1][0];
            v[zhujianID][3] = value[0][0] * value[0][1] + value[1][0] * value[1][1];
        } else {//此主件有2个附件
            w[zhujianID][0] = value[0][0];
            v[zhujianID][0] = value[0][0] * value[0][1];
            w[zhujianID][1] = value[0][0] + value[1][0];
            v[zhujianID][1] = value[0][0] * value[0][1] + value[1][0] * value[1][1];
		  //bug2:写迷糊了，这儿出了点小错
            w[zhujianID][2] = value[0][0] + value[2][0];
            v[zhujianID][2] = value[0][0] * value[0][1] + value[2][0] * value[2][1];
            w[zhujianID][3] = value[0][0] + value[1][0] + value[2][0];
            v[zhujianID][3] = value[0][0] * value[0][1] + value[1][0] * value[1][1] +
                              value[2][0] * value[2][1];

        }
        zhujianID++;
    }
  //感觉上面这一堆逻辑写的过于复杂，出了很多bug，调试了半个小时。不知道有没有简单的写法。
    vector<vector<int> > dp(zhujianNum + 1, vector<int>(n + 1));
  //dp数组全是0，所以不需要初始化第一行和第一列。
  //bug3:加上初始化第一行第一列的语句，会导致超时
    for (int i = 1; i <= zhujianNum; i++) {
        for (int j = 10; j <= n ; j += 10) {
            int max_xuanzhongDP = 0;
            for (int k = 0; k < 4; k++) {
                if (j >= w[i][k]) {
                    max_xuanzhongDP = max(max_xuanzhongDP, dp[i - 1][j - w[i][k]] + v[i][k]);
                }
            }
            dp[i][j] = max(dp[i - 1][j], max_xuanzhongDP);
        }
    }
    cout << dp[zhujianNum][n];
    return 0;
}
// 64 位输出请用 printf("%lld")