题解 | #购物单#

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

int main() {
    int P, n;
    cin >> P >> n;

    vector<int> price(n);//价格
    vector<int> value(n);//重要度
    vector<int> temp(n);//p或者q
    vector<int> parent;//主件
    vector<vector<int>> children(n, vector<int>());//主件的附件集合

    for (int i = 0; i < n; i++) {
        cin >> price[i] >> value[i] >> temp[i];
        if (temp[i] != 0)children[temp[i] - 1].emplace_back(i);
        else parent.emplace_back(i);
    }

    //懒得初始化，使用一维
  	//dp[i][k]=max(dp[i-1][k],dp[i-1][k-price[i]]+value[i])
    vector<int> dp(P + 1, 0);
    for (int i = 0; i < parent.size(); i++) {
        int index = parent[i];
	  
        for (int k = P; k >= price[index]; k -= 10) {

            //附件所有可能的取法（包括一件也不取）
            for (int m = 0; m < 1 << children[index].size(); m++) {
                int weight = price[index];
                int val = value[index] * price[index];

                //一种情况的一个附件，是否选取
                for (int pos = 0; pos < children[index].size(); pos++) {
                    if (m & (1 << pos)) { //如果第pos位为0则if为假
                        weight += price[children[index][pos]];
                        val += value[children[index][pos]] * price[children[index][pos]];
                    }
                }
                if (k >= weight) dp[k] = max(dp[k], dp[k - weight] + val);
            }
        }
    }
    cout << dp[P] << endl;
    return 0;
}