首页 > 代码库 > 树形dp hdu1561
树形dp hdu1561
有的堡垒攻克需要攻克另一个堡垒，形成一个森林，最多攻克m个堡垒，求获得宝物的最大价值。
1，以0做根将森林形成树；
2，用背包计算当前节点下需要攻克k个堡垒能获得的宝物最大价值，但是注意同一个根节点的情况不能够先后放入背包，否则会有比如1节点选2个和选三个形成了选5个，也就是某些节点重复计算了。所以要在back第j格时将所有种k依次放入，j--；
#include<iostream>#include<string.h>#include<stdio.h>#include<vector>using namespace std;const int maxa = 205;int dp[maxa][maxa];int back[maxa][maxa];int vis[maxa][maxa];int v[maxa];vector<int> edge[maxa];int numb[maxa];int dfs(int x, int num ){//printf("%d %d\n", x, num); if(vis[x][num] || num == 0) return dp[x][num]; memset(back[x], 0, sizeof(back[x])); for(int i = 0; i < edge[x].size(); i ++){ int k = edge[x][i];//printf("%d ", k); int last = -1; for(int h = num-1; h >= 1; h--){ for(int j = 1; j <= h && j <= numb[k]; j++){ int a = dfs(k, j); back[x][h] = max(back[x][h], back[x][h-j] + a);//printf("%d ", back[h]); }//puts(""); } } vis[x][num] = 1; return dp[x][num] = back[x][num-1]+v[x];}int dfs1(int x){ int sum = 0; for(int i = 0; i < edge[x].size(); i++){ int k = edge[x][i]; sum += dfs1(k); } return numb[x] = sum +1;}int main(){int n, m; //freopen("in.cpp", "r", stdin); while(scanf("%d%d", &n, &m), n+m){ memset(vis, 0, sizeof(vis)); for(int i =0; i <= n; i++) edge[i].clear(); for(int i =1; i <= n; i++){ int a, b; scanf("%d%d", &a, &b); v[i] = b; edge[a].push_back(i); } dfs1(0); memset(dp, 0, sizeof(dp)); printf("%d\n", dfs(0, m+1)); /* for(int i = 0; i <= n; i++){ printf("*%d ", numb[i]); }*/ }}
树形dp hdu1561
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。