题解 | #购物单#

#include <bits/stdc++.h>
using namespace std;
const int maxm = 64, maxn = 32004;
int N, m;

struct Stuff {
    int v, p, q;
    vector<Stuff> son;
} stuff[maxm];

struct Node {
    int c, w;

    Node(int c, int w) : c(c), w(w)
    {
    }
};

void dfs(vector<Node> &g, const Stuff &stu, int p_son, int curr_cost, int curr_weight)
{
    if (p_son == (int) stu.son.size()) {
        g.emplace_back(curr_cost, curr_weight);
        return;
    }
    dfs(g, stu, p_son + 1, curr_cost, curr_weight);
    dfs(g, stu, p_son + 1, curr_cost + stu.son[p_son].v, curr_weight + stu.son[p_son].v * stu.son[p_son].p);
}

void Add(vector<vector<Node>> &group, const Stuff &stu)
{
    group.emplace_back();
    vector<Node> &g = group.back();
    dfs(g, stu, 0, stu.v, stu.v * stu.p);
}

int solve(int N)
{
    vector<vector<Node>> group;
    for (int i = 0; i < m; ++i)
        if (stuff[i].q == 0)
            Add(group, stuff[i]);
    vector<int> F(N + 1);
    for (size_t k = 0; k != group.size(); ++k)
        for (int v = N; v >= 0; --v)
            for (Node &node : group[k])
                if (v >= node.c)
                    F[v] = max(F[v], F[v - node.c] + node.w);
    return F.back();
}

int main()
{
    cin >> N >> m;
    for (int i = 0; i < m; ++i) {
        cin >> stuff[i].v >> stuff[i].p >> stuff[i].q;
        if (stuff[i].q)
            stuff[stuff[i].q - 1].son.push_back(stuff[i]);
    }
    cout << solve(N) << endl;
}