题解 | #购物单#

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

struct Condition{
    int one;
    int two;
    int three;
    int four;
};

struct Goods{
    Condition price;
    Condition weight;
    int key;
};

bool cmp(Goods num1, Goods num2){
    return num1.key < num2.key;
}

int main(){
    int n, m;
    while(cin >> m >> n){
        vector<Goods> goods(n + 1);
        vector<Goods> m1goods;
        for(int i = 1; i <= n; i++){
            cin >> goods[i].weight.one >> goods[i].price.one >> goods[i].key;
            goods[i].price.one = goods[i].price.one * goods[i].weight.one;
            goods[i].price.two = goods[i].price.three = goods[i].price.four = goods[i].price.one;
            goods[i].weight.two = goods[i].weight.three = goods[i].weight.four = goods[i].weight.one;
        }
        for(int i = 1; i < n + 1; i++){
            if(goods[i].key != 0 && goods[goods[i].key].price.one == goods[goods[i].key].price.two){//出现的第一个附件
                goods[goods[i].key].price.two = goods[i].price.one + goods[goods[i].key].price.one;
                goods[goods[i].key].weight.two = goods[i].weight.one + goods[goods[i].key].weight.one;
            }else if(goods[i].key != 0){//出现的第二个附件
                goods[goods[i].key].price.three = goods[i].price.one + goods[goods[i].key].price.one;
                goods[goods[i].key].price.four = goods[i].price.one + goods[goods[i].key].price.two;
                goods[goods[i].key].weight.three = goods[i].weight.one + goods[goods[i].key].weight.one;
                goods[goods[i].key].weight.four = goods[i].weight.one + goods[goods[i].key].weight.two;
            }else{

            }
        }
        for(int i = 1; i < n + 1; i++){
            if(goods[i].key == 0)
                m1goods.push_back(goods[i]);
        }
        int **dp = new int*[m1goods.size()];
        for(int i = 0; i < m1goods.size() + 1; i++){
            dp[i] = new int[m + 1];
        }
        for(int i = 0; i <= m1goods.size(); i++)
            for(int j = 0; j < m + 1; j++)
                dp[i][j] = 0;
        int temp = 0;
        for(int i = 1; i <= m1goods.size(); i++){
            temp = m1goods[i - 1].weight.one <= 1 && m1goods[i - 1].price.one > temp ? m1goods[i - 1].price.one : temp; 
            dp[i][1] = temp;
        }
        for(int i = 1; i < m + 1; i++)
            dp[1][i] = max(
                max(m1goods[0].weight.three <= i ? m1goods[0].price.three : 0, 
                    m1goods[0].weight.four <= i ? m1goods[0].price.four : 0), 
                max(m1goods[0].weight.one <= i ? m1goods[0].price.one : 0, 
                    m1goods[0].weight.two <= i ? m1goods[0].price.two : 0)
                );//取四种情况中的最大值。
        if (m1goods.size() == 1)    return 0;
        int ans = 0;
        for(int i = 2; i <= m1goods.size(); i++){
            for(int j = 2; j <= m; j++){
                dp[i][j] = max(dp[i - 1][j], 
                            max(
                                max(m1goods[i - 1].weight.one <= j ? dp[i - 1][j - m1goods[i - 1].weight.one] + m1goods[i - 1].price.one : 0, 
                                    m1goods[i - 1].weight.two <= j ? dp[i - 1][j - m1goods[i - 1].weight.two] + m1goods[i - 1].price.two : 0),
                                max(m1goods[i - 1].weight.three <= j ? dp[i - 1][j - m1goods[i - 1].weight.three] + m1goods[i - 1].price.three : 0, 
                                    m1goods[i - 1].weight.four <= j ? dp[i - 1][j - m1goods[i - 1].weight.four] + m1goods[i - 1].price.four : 0)
                                ));
                ans = dp[i][j] > ans ? dp[i][j] : ans;
            }
        }
        cout << ans;
    }
    return 0;
}