```cpp
#include <bits/stdc++.h>
using namespace std;
int a[65], b[65], pr[65], n, m;
int c[65][2], d[32005];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int v, p, q;
scanf("%d%d%d", &v, &p, &q);
a[i] = v * p;
pr[i] = v;
if (!c[q][0]) c[q][0] = i;
else c[q][1] = i;
b[i] = q;
}
for (int i = 1; i <= m; i++) {
int p = b[i], ls = c[p][0], rs = c[p][1];
for (int j = 0; j <= n; j++) {
if (p) {
if (pr[p] <= j) d[j] = max(d[j], d[j - pr[p]] + a[p]);
if (ls && pr[p] + pr[ls] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls]] + a[p] + a[ls]);
if (rs && pr[p] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[rs]] + a[p] + a[rs]);
if (ls && rs && pr[p] + pr[ls] + pr[rs] <= j) d[j] = max(d[j], d[j - pr[p] - pr[ls] - pr[rs]] + a[p] + a[ls] + a[rs]);
} else if (pr[i] <= j) {
d[j] = max(d[j], d[j - pr[i]] + a[i]);
}
}
}
printf("%d\n", d[n]);
return 0;
}
```
by Qing_fy @ 2021-07-26 20:48:09
希丰展？使md
by AF0x3b800001 @ 2021-07-26 21:12:25
题目中应该理解为01背包，您是不是理解为完全背包了（
by baoziwu2 @ 2021-07-26 22:00:47