kguniverse @ 2020-02-22 14:52:24
#include<iostream>
#include<algorithm>
using namespace std;
#define maxm 65
#define maxn 32001
int v[maxm], w[maxm], q[maxm], dp[maxm][maxn], fujian[maxm][maxm], cnt[maxm], zhujian[maxm];
int max1 (int a, int b, int c) {
if (a < b) a = b;
if (a < c) a = c;
return a;
}
int main() {
int n, m;
cin >> n >> m;
int cnt1 = 1;
for (int i = 1; i <= m; i++) {
cin >> v[i] >> w[i] >> q[i];
if (q[i]) fujian[q[i]][cnt[q[i]]++] = i;
else zhujian[cnt1++] = i;
}
int i;
for (i = 1; zhujian[i]; i++) {
for (int t = 0; t <= n; t++) {
if (t < v[zhujian[i]]) {
dp[zhujian[i]][t] = dp[zhujian[i - 1]][t];
continue;
}
else dp[zhujian[i]][t] = max1(dp[zhujian[i]][t], dp[zhujian[i - 1]][t], dp[zhujian[i - 1]][t - v[zhujian[i]]] + v[zhujian[i]] * w[zhujian[i]]);
if (dp[zhujian[i]][t] == dp[zhujian[i - 1]][t - v[zhujian[i]]] + v[zhujian[i]] * w[zhujian[i]]) { //当选择了主件时,状态转移方程的对象变为附件
for (int j = 0; fujian[zhujian[i]][j]; j++) {
for (int r = 0; r <= n - v[zhujian[i]]; r++) {
if (r < v[fujian[zhujian[i]][j]]) continue;
dp[zhujian[i]][r + v[zhujian[i]]] = max(dp[zhujian[i]][r + v[zhujian[i]]], dp[zhujian[i]][r + v[zhujian[i]] - v[fujian[zhujian[i]][j]]]);
}
}
}
}
}
int res = 0;
for (int r = 0; r <= n; r++) {
if (res < dp[zhujian[i - 1]][r]) res = dp[zhujian[i - 1]][r];
}
cout << res;
}
by LinkCutTree @ 2020-02-22 15:01:22
顺便问一句,这题的正解是不是树形背包?
by cmll02 @ 2020-02-22 15:01:46
BUSHI
by kguniverse @ 2020-02-22 16:54:11
刚刚看了答案感觉我的思路和他差不多,但是答案用的是结构体实现的,实在没找出来我的代码问题出在哪里惹。。