30WA

戳我看题目

#include <bits/stdc++.h>
#define MAXN 32000
using namespace std;
int fa[MAXN], dp[MAXN], w[MAXN], v[MAXN], son[MAXN][3], cnt[MAXN];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &w[i], &v[i], &fa[i]);
		v[i] *= w[i];
		if (fa[i])
			son[fa[i]][++cnt[i]] = i;
	}
	for (int i = 1; i <= m; i++)
		if (!fa[i])
			for (int j = n; j >= w[i]; j--) {
				dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
				if (j >= w[i] + w[son[i][1]])
					dp[j] = max(dp[j], v[i] + v[son[i][1]] + dp[j - w[i] - w[son[i][1]]]);
				if (j >= w[i] + w[son[i][2]])
					dp[j] = max(dp[j], v[i] + v[son[i][2]] + dp[j - w[i] - w[son[i][2]]]);
				if (j >= w[i] + w[son[i][1]] + w[son[i][2]])
					dp[j] = max(dp[j], v[i] + v[son[i][1]] + v[son[i][2]] + dp[j - w[i] - w[son[i][1]] - w[son[i][2]]]);
			}
	printf("%d\n", dp[n]);
	return 0;
}