题解 | #购物单#

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

int main() {
    int N, m; //N表示总钱数，m表示可购买的物品的个数
    cin >> N >> m;
    vector<int> prices(m);
    vector<int> importance(m);
    vector<int> master(m);
    for (int i = 0; i < m; ++i) {
        cin >> prices[i] >> importance[i] >> master[i];
    }
    //input
    vector<vector<int>> prices_m(m);
    vector<vector<int>> importance_m(m);
    int ms_num = 0;
    for (int i = 0; i < m; i++) {
        if (master[i] == 0) {
            ms_num++;
            prices_m[i].push_back(prices[i]);
            importance_m[i].push_back(importance[i]* prices[i]);
        }
    }
    
    for (int i = 0; i < m; i++) {
        int mst = master[i];
        if (mst != 0) {
            vector<int> p_buff = prices_m[mst - 1];
            for (int p : p_buff) {
                prices_m[mst - 1].push_back(p + prices[i]);
            }
            ;
            vector<int> im_buff = importance_m[mst - 1];
            for (int im : im_buff) {
                importance_m[mst - 1].push_back(im + importance[i]* prices[i]);
            }
        }
    }
    vector<int> dp(N + 1);
    vector<int> dp_buff(N + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < N + 1; ++j) {
            int idx_buff;
            int imp_buff;
            vector<int> value;
            value.push_back(dp[j]);
            for (int k = 0; k < prices_m[i].size(); k++) {
                if (j >= prices_m[i][k])
                {
                    idx_buff = j - prices_m[i][k];
                    imp_buff = importance_m[i][k];
                    value.push_back(dp_buff[idx_buff] + imp_buff);

                }
            }
            dp[j] = *max_element(value.begin(), value.end());
        }
        dp_buff = dp;
    }
    //process
    cout << dp[N];
    cin.get();
    //output
}
// 64 位输出请用 printf("%lld")