题解 | #购物单#

#include <array>
#include <iostream>
using namespace std;

const int N = 65;
array<array<int, 33000>, N> f;
array<array<int, 5>, N>
a={0}; //a[i][0]表示编号为i的主件拥有的附件的数量，其余为附件编号
array<int, 65>pri={0}, impo={0}, qq={0};

int n, m;
int main() {
    cin >> n >> m;
    int v, p, q;
    for (int i = 1; i <= m; i++) { //初始化
        cin >> v >> p >> q;
        pri[i] = v;
        impo[i] = p;
        qq[i] = q;
        if (q != 0) {
            a[q][0]++;
            a[q][a[q][0]] = i;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (qq[i] == 0) {
            for (int j = 0; j <= n; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= pri[i])
                    f[i][j] = max(f[i][j], f[i - 1][j - pri[i]] + pri[i] * impo[i]);
                if (a[i][0] == 1 && j >= (pri[i] + pri[a[i][1]]))
                    f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]);
                if (a[i][0] == 2) {
                    if (j >= (pri[i] + pri[a[i][1]]))
                        f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]);
                    if (j >= (pri[i] + pri[a[i][2]]))
                        f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][2]]] + pri[i] * impo[i] + pri[a[i][2]] * impo[a[i][2]]);
                    if (j >= (pri[i] + pri[a[i][1]]+ pri[a[i][2]]))
                        f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]- pri[a[i][2]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]+pri[a[i][2]] * impo[a[i][2]]);
                }
            }
        }
        else
            for(int j=0;j<=n;j++)
                f[i][j]=f[i-1][j];
    }
    cout<<f[m][n]<<endl;
    return 0;
    
}
// 64 位输出请用 printf("%lld")