洛谷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("%d\n", 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("%d\n", dp[1][Q]);

	return 0;

}