首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。