首页 > 代码库 > 11782 - Optimal Cut(树形DP+记忆化搜索)

11782 - Optimal Cut(树形DP+记忆化搜索)

题目链接:11782 - Optimal Cut

题意:按前序遍历给定一棵满二叉树,现在有k次,可以选k个节点,获得他们的权值,有两个条件:
1、一个节点被选了,他的子节点就不能选了。
2、最终选完后,根到所有叶子的路径上,都要有一个被选的节点。
思路:树形dp,dp[u][k]代表在结点u,可以选k个节点,那么就分两种情况
选u节点,dp[u][k] = node[u];
选子节点之和,那么就把k次分配给左右孩子,dp[u][k] = max(dp[u][k], dp[u][i], dp[u][k - i]) (1<= i < k)
代码:
#include <stdio.h>
#include <string.h>

#define max(a,b) ((a)>(b)?(a):(b))
const int N = (1<<20) + 5;
const int M = 25;
int h, k, node[N], dp[N][M], vis[N][M];

void build(int u, int d) {
	memset(vis[u], 0, sizeof(vis[u]));
	if (d == h) return;
	scanf("%d", &node[u]);
	build(u * 2 + 1, d + 1);
	build(u * 2 + 2, d + 1);
}

void dfs(int u, int k, int d) {
	if (vis[u][k]) return;
	vis[u][k] = 1;
	dp[u][k] = node[u];
	if (d + 1 == h) return;
	for (int i = 1; i < k; i++) {
		int l = u * 2 + 1;
		int r = u * 2 + 2;
		dfs(l, i, d + 1);
		dfs(r, k - i, d + 1);
		dp[u][k] = max(dp[u][k], dp[l][i] + dp[r][k - i]);
	}
}

int main() {
	while (~scanf("%d", &h) && h != -1) {
		h++;
		scanf("%d", &k);
		build(0, 0);
		dfs(0, k, 0);
		printf("%d\n", dp[0][k]);
	}
	return 0;
}