题解P1064 Noip 2006 提高组 金明的预算方案

输入：
n=1000, m=5
物品：
1: v=800, p=2, q=0  (主件)
2: v=400, p=5, q=1  (附件，属于主件1)
3: v=300, p=5, q=1  (附件，属于主件1)
4: v=400, p=3, q=0  (主件)
5: v=500, p=2, q=0  (主件)

主件1的购买方案：
1. 只主件： price=800, value=800*2=1600
2. 主件+附件2： price=800+400=1200, value=1600+400*5=3600
3. 主件+附件3： price=800+300=1100, value=1600+300*5=3100
4. 主件+附件2+附件3： price=800+400+300=1500, value=1600+2000+1500=5100

主件4的方案：只主件： price=400, value=400*3=1200
主件5的方案：只主件： price=500, value=500*2=1000

分组背包DP过程（简化）：
初始dp全0。
处理主件1组：更新后，dp[800]=1600, dp[1200]=3600（但n=1000，所以1200和以上不会影响最终结果）
处理主件4组：更新后，dp[400]=1200, dp[800]=max(1600, dp[400]+1200)=max(1600, 1200+1200=2400)=2400? 
  注意：dp[400]在处理主件4组时还是0（因为倒序更新，dp[400]尚未被当前组更新），所以dp[800]仍为1600。
  实际上，更准确地说，处理主件4组时，对于j=800，dp[800] = max(1600, dp[400]+1200)=max(1600, 0+1200)=1600。
  之后dp[900] = max(0, dp[500]+1200)，其中dp[500]可能为0。
处理主件5组：更新后，dp[500]=1000, dp[900]=max(dp[900], dp[400]+1000)=max(1200, 1200+1000=2200)=2200。
最终dp[1000]可能是2200（由dp[500]+主件5? 但dp[500]=1000，加上主件5得2000；或者dp[400]+主件5? dp[400]=1200，加上主件5得2200）。
所以最优方案为主件4+主件5，总价900，价值2200。

#include <bits/stdc++.h>
using namespace std;

struct Option {
    int price;   // 方案总价格
    int value;   // 方案总价值（价格*重要度之和）
};

int main() {
    // IO加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> v(m + 1), p(m + 1), q(m + 1);
    vector<vector<int>> attachments(m + 1); // attachments[主件编号]存储附件编号

    // 读入数据，建立主件与附件的关系
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] != 0) {
            attachments[q[i]].push_back(i);
        }
    }

    // dp[j]: 花费不超过j元的最大价值
    vector<int> dp(n + 1, 0);

    // 遍历每个物品，只处理主件（q[i]==0）
    for (int i = 1; i <= m; ++i) {
        if (q[i] != 0) continue; // 跳过附件

        // 生成当前主件的所有购买方案
        vector<Option> options;

        // 方案1: 只买主件
        options.push_back({v[i], v[i] * p[i]});

        int num_att = attachments[i].size();

        // 处理附件组合
        if (num_att >= 1) {
            int att1 = attachments[i][0];
            // 方案2: 主件 + 附件1
            options.push_back({v[i] + v[att1], 
                               v[i] * p[i] + v[att1] * p[att1]});

            if (num_att >= 2) {
                int att2 = attachments[i][1];
                // 方案3: 主件 + 附件2
                options.push_back({v[i] + v[att2], 
                                   v[i] * p[i] + v[att2] * p[att2]});
                // 方案4: 主件 + 两个附件
                options.push_back({v[i] + v[att1] + v[att2], 
                                   v[i] * p[i] + v[att1] * p[att1] + v[att2] * p[att2]});
            }
        }

        // 分组背包更新：对每个组，容量倒序，枚举组内所有方案
        for (int j = n; j >= 0; --j) {
            for (const Option& opt : options) {
                if (j >= opt.price) {
                    dp[j] = max(dp[j], dp[j - opt.price] + opt.value);
                }
            }
        }
    }

    cout << dp[n] << '\n';

    return 0;
}