首页 > 代码库 > HDU 4169 Wealthy Family
HDU 4169 Wealthy Family
题意:
n个节点的树 每个节点上有个价值 要求选出k个两两互相没有祖孙关系的节点 使得价值和最大
思路:
明显的树形dp 如果用dp[fa][i]表示fa子树取i个点的最大价值和 则有转移 dp[fa][i]=max(dp[son][k]+dp[fa][i-k])
但是如果这样开数组会MLE 所以本题猥琐的使用dfs内部开数组的方式 这样借助全局变量的帮助 我们可以避免MLE
(其实如果树是一条链照样MLE 这个方法很不科学 但是数据水 能AC)
如果是现场赛反正电脑闲着也是闲着一定要写这个不要脸的算法!!
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> #include<bitset> using namespace std; #define N 310 #define M 150010 int n, m; int sz, save[N], tmp[N], val[M]; int tot, head[M]; struct edge { int v, next; } ed[M]; void add(int u, int v) { ed[tot].v = v; ed[tot].next = head[u]; head[u] = tot++; } void dfs(int u) { int dp[N]; memset(dp, 0, sizeof(dp)); int cnt = 0; for (int i = head[u]; ~i; i = ed[i].next) { int v = ed[i].v; dfs(v); memset(tmp, 0, sizeof(tmp)); for (int j = 0; j <= cnt; j++) { for (int k = 0; k <= sz && j + k <= m; k++) { tmp[j + k] = max(tmp[j + k], dp[j] + save[k]); } } cnt = min(m, cnt + sz); memcpy(dp, tmp, sizeof(int) * (cnt + 1)); } dp[1] = max(dp[1], val[u]); if (!cnt) cnt = 1; sz = cnt; memcpy(save, dp, sizeof(int) * (cnt + 1)); } int main() { while (~scanf("%d%d", &n, &m)) { tot = 0; memset(head, -1, sizeof(int) * (n + 1)); for (int i = 1; i <= n; i++) { int fa; scanf("%d%d", &fa, &val[i]); add(fa, i); } memset(save, 0, sizeof(save)); dfs(ed[head[0]].v); if (save[m]) printf("%d\n", save[m]); else printf("impossible\n"); } return 0; }
HDU 4169 Wealthy Family
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。