洛谷2015（树形dp）

要点

• 是树形的考虑dfs
• 分为取一枝，取两枝两种情况，将它们的合法情况进行暴举取最好答案即可，貌似我乱搞得相当冗……
• 顺手记忆化
• 正解应该是树上背包

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <vector>
#define pb push_back
using namespace std;
int N, Q, cost[101][101], size[101], dp[101][101];
vector<int> adj[101];
int dfs(int cur, int fa, int rest) {
if (rest <= 0)
return 0;
if (dp[cur][rest] >= 0) return dp[cur][rest];
int res = 0;
vector<int> v;
for (int son : adj[cur]) {
if (son == fa)
continue;
if (size[son] + 1 >= rest)
res = max(res, dfs(son, cur, rest - 1) + cost[cur][son]);
v.pb(son);
}
if (v.size() == 2 && rest >= 2) {
int r = rest - 2;
for (int i = 0; i <= min(r, size[v[0]]); i++)
if (r - i <= size[v[1]]) {
res = max(res, dfs(v[0], cur, i) + dfs(v[1], cur, r - i) + cost[cur][v[0]] + cost[cur][v[1]]);
}
}
return dp[cur][rest] = res;
}
int main() {
scanf("%d %d", &N, &Q);
if (Q == N) Q--;
for (int i = 1; i < N; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
cost[u][v] = cost[v][u] = c;
adj[u].pb(v), adj[v].pb(u);
}
function<void(int, int)> S = [&](int cur, int fa) {
size[cur] = 0;
for (int son : adj[cur])
if (son != fa) {
S(son, cur);
size[cur] += size[son] + 1;
}
};
S(1, 0);
memset(dp, -1, sizeof dp);
printf("%dn", dfs(1, 0, Q));
return 0;
}

树上背包版，j-k要使用上个儿子的所以j倒序：

#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
int N, Q, cost[101][101], dp[101][101];
vector<int> adj[101];
int dfs(int cur, int fa) {
int ret = 0;
for (int son : adj[cur]) {
if (son == fa)
continue;
int size = dfs(son, cur);
ret += size + 1;
for (int j = min(Q, ret); j; j--) {
for (int k = 1; k <= min(j, size + 1); k++) {
dp[cur][j] = max(dp[cur][j], dp[cur][j - k] + dp[son][k - 1] + cost[cur][son]);
}
}
}
return ret;
}
int main() {
scanf("%d %d", &N, &Q);
if (Q == N) Q--;
for (int i = 1; i < N; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
cost[u][v] = cost[v][u] = c;
adj[u].pb(v), adj[v].pb(u);
}
dfs(1, 0);
printf("%dn", dp[1][Q]);
return 0;
}