题解 | #购物单#

#include <iostream>
#include <vector>
#include<cmath>
using namespace std;
#define max(N1,N2) N1>N2?N1:N2
struct Thing {
  public:
    int price;
    int target;
    int Value;
    int sub1 = -1;
    int sub2 = -1;
};

int main() {
    int money, n;
    cin >> money >> n;
    int len = n;
    vector<Thing> things;
    for (int i = 0; i < len; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        Thing thing;
        thing.price = a;
        thing.target = c;
        thing.Value = a * b;
        things.push_back(thing);
    }
    for(int i = 0; i < len; i++)
    {
        if(things[i].target!=0)
        {
            if(things[things[i].target-1].sub1==-1)
                things[things[i].target-1].sub1 = i;
            else
                things[things[i].target-1].sub2 = i;

        }
    }
    vector<vector<int>> f;//f[i][j]初始化
    for (int i = 0; i < n + 1; i++) {
        vector<int> ins(money + 1, 0);
        f.push_back(ins);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= money; j++) {
            f[i][j] = f[i - 1][j];
            if (things[i - 1].target != 0) 
            {
                continue;
            }
            if(j >= things[i - 1].price) 
            {
                f[i][j] = max(f[i][j],f[i - 1][j - things[i - 1].price] + things[i - 1].Value);
            }
            if(things[i - 1].sub1!=-1 &&j >= things[things[i - 1].sub1].price + things[i - 1].price) 
            {
                f[i][j] = max(f[i][j],f[i - 1][j - things[i - 1].price - things[things[i - 1].sub1].price] + things[i- 1].Value + things[things[i - 1].sub1].Value);
            }
            if(things[i - 1].sub2!=-1 &&j >= things[things[i - 1].sub2].price + things[i - 1].price) 
            {
                f[i][j] = max(f[i][j],f[i - 1][j - things[i - 1].price - things[things[i - 1].sub2].price] + things[i- 1].Value + things[things[i - 1].sub2].Value);
                }
            if(things[i-1].sub2!=-1 &&j>=things[things[i - 1].sub2].price + things[i - 1].price+things[things[i - 1].sub1].price)
            {
                f[i][j] = max(f[i][j],f[i - 1][j - things[i - 1].price - things[things[i - 1].sub2].price-things[things[i - 1].sub1].price] + things[i- 1].Value + things[things[i - 1].sub2].Value+things[things[i - 1].sub1].Value);
            }
        }

    }
    cout<<f[n][money];








}
// 64 位输出请用 printf("%lld")