题解 | #购物单#

#include <iostream>
using namespace std;
class Goods {
  public:
    int v;
    int p;
    int q;
    Goods() {
        v = p = q = -1;
    }
    void set(int v1, int p1, int q1) {
        this->v = v1;
        this->p = p1;
        this->q = q1;
    }
};
int maxx(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int N, m, v, p, q, i, j;
    int T[35000];
    Goods G[65][3];
    cin >> N >> m;
    for (i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        if (q == 0) G[i][0].set(v, p, q);
        else if (G[q][1].v == -1) G[q][1].set(v, p, q);
        else G[q][2].set(v, p, q);
    }
    for (i = 1; i <= m; i++) {
        if (G[i][0].v == -1) continue;
        for (j = N; j >= G[i][0].v; j--) {
            T[j] = maxx(T[j], T[j - G[i][0].v] + G[i][0].v * G[i][0].p);
            if (G[i][1].v != -1 &&
                    j >= (G[i][0].v + G[i][1].v)) T[j] = maxx(T[j],
                                T[j - G[i][0].v - G[i][1].v] + G[i][0].v * G[i][0].p + G[i][1].v * G[i][1].p);
            if (G[i][2].v != -1 &&
                    j >= (G[i][0].v + G[i][2].v)) T[j] = maxx(T[j],
                                T[j - G[i][0].v - G[i][2].v] + G[i][0].v * G[i][0].p + G[i][2].v * G[i][2].p);
            if (G[i][2].v != -1 &&
                    j >= (G[i][0].v + G[i][1].v + G[i][2].v)) T[j] = maxx(T[j],
                                T[j - G[i][0].v - G[i][1].v - G[i][2].v] + G[i][0].v * G[i][0].p + G[i][1].v * G[i][1].p + G[i][2].v * G[i][2].p);
        }
    }
    cout<<T[N]<<endl;
    return 0;
}

累