题解 | #购物单#

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
    int a, b;
    while (cin >> a >> b)
    {
        vector<int>c, d, e;
        for (int i = 0; i < b; i++)
        {
            int f, g, h;
            cin >> f >> g >> h;
            c.push_back(f);
            d.push_back(g);
            e.push_back(h);
        }
        vector<vector<int>>f;
        vector<vector<int>>w;
        vector<int>g;
        map<int, int>h, l;
        for (int i = 0; i < b; i++)
        {
            int a = c[i] * d[i];
            g.push_back(a);
        }
        for (int i = 0; i < b; i++)
        {
            if (e[i] == 0)
            {
                vector<int>a;
                vector<int>u;
                u.push_back(c[i]);
                w.push_back(u);
                a.push_back(g[i]);
                f.push_back(a);
                int n = f.size();
                h[i+1] = n - 1;
                l[n - 1] = i+1;
            }
        }
         for (int i = 0; i < b; i++)
        {
             if (e[i] != 0)
            {
               
                if (f[h[e[i]]].size() == 1)
                {
                   // f[h[e[i]]].push_back(g[i]);
                   // w[h[e[i]]].push_back(c[i]);
                    f[h[e[i]]].push_back(g[i] + f[h[e[i]]][0]);
                    w[h[e[i]]].push_back(c[i] + w[h[e[i]]][0]);
                }
                else if (f[h[e[i]]].size() == 2)
                {
                   // f[h[e[i]]].push_back(g[i]);
                  //  w[h[e[i]]].push_back(c[i]);
                    f[h[e[i]]].push_back(g[i] + f[h[e[i]]][0]);
                    w[h[e[i]]].push_back(c[i] + w[h[e[i]]][0]);
                    //f[h[e[i]]].push_back(g[i] + f[h[e[i]]][1]);
                   // w[h[e[i]]].push_back(c[i] + w[h[e[i]]][1]);
                    f[h[e[i]]].push_back(g[i]  + f[h[e[i]]][1]);
                    w[h[e[i]]].push_back(c[i] + w[h[e[i]]][1]);
                }
            }
        }
       int v[100][10000];
        for (int i = 0; i < f.size(); i++)
        {
            for (int j = 0; j <= a; j += 10)
            {
                if (i == 0)
                {
                    v[i][j / 10] = 0;
                }
                else if (i > 0)
                {
                   v[i][j / 10] =v[i - 1][j / 10];
                }
                for (int m = 0; m < f[i].size(); m++)
                {
                    int t = 0;
                    if (j >= w[i][m])
                    {
                        if (i == 0)
                        {
                            t = max(0, f[i][m]);
                        }
                        else if (i > 0)
                        {
                            int x = v[i - 1][j / 10], y =v[i - 1][(j - w[i][m]) / 10] + f[i][m];
                            t = max(x, y);
                        }
                    }
                    if (t > v[i][j / 10])
                    {
                        v[i][j / 10] = t;
                    }
                }

            }
        }
        cout <<v[f.size() - 1][a / 10];
    }
    return(0);
}