好贷网好贷款

POJ-3345 Bribing FIPA(Tree dp + 背包)

发布时间:2016-12-5 8:33:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ-3345 Bribing FIPA(Tree dp + 背包)",主要涉及到POJ-3345 Bribing FIPA(Tree dp + 背包)方面的内容,对于POJ-3345 Bribing FIPA(Tree dp + 背包)感兴趣的同学可以参考一下。

题目意思,给定一棵树,节点都有一个值val,表示攻占掉以该节点为根的子树(攻占了这棵子树所有的结点)所需要的最少值,问至少需要攻占m个字节需要的最少值。 类似于POJ-1155(http://blog.csdn.net/wrong_answer/article/details/10824753),树上做0-1背包,转移方程也一致。不过是背包完毕之后,需要判断一下dp[root][sum]与根节点val值的大小,因为只需要val就可以拿到sum个结点,这是处理的特殊地方。 读入很恶心,处理需谨慎,使用sscanf处理会方便很多,字符串使用map映射处理。 #include <stdio.h> #include <vector> using namespace std; const int MAXN = 3005; const int INF = 0x3f3f3f3f; struct node { int end,val; }; vector<node> v[MAXN]; int cost[MAXN],dp[MAXN][MAXN]; int n,m; inline node make_node(int end,int val) { node a; a.end = end;a.val = val; return a; } inline int max(int a,int b){ return a < b ? b : a; } int dfs(int root) { int sum = 1; vector<node>::iterator it; for(it=v[root].begin();it!=v[root].end();it++) { sum += dfs((*it).end); } for(it=v[root].begin();it!=v[root].end();it++) for(int j = sum;j >= 0;j--) for(int k = 0;k <= j;k++) dp[root][j] = max(dp[root][j],dp[(*it).end][k]+dp[root][j-k]-(*it).val); //printf("root = %d sum = %d\n",root,sum); return sum; } int main() { int num,a,b; while(scanf("%d%d",&n,&m) == 2) { for(int i = 1;i <= n;i++) v[i].clear(); for(int i = 1;i <= n-m;i++) { scanf("%d",&num); for(int j = 1;j <= num;j++) { scanf("%d%d",&a,&b); v[i].push_back(make_node(a,b)); } } for(int i = n-m+1;i <= n;i++) scanf("%d",&cost[i]); for(int i = 1;i <= n;i++) for(int j = 0;j <= n;j++) dp[i][j] = -INF; for(int i = 1;i <= n;i++) dp[i][0] = 0; for(int i = n-m+1;i <= n;i++) dp[i][1] = cost[i]; dfs(1); bool find = 0; for(int i = n;i >= 1;i--){ if(dp[1][i] >= 0){ find = 1; printf("%d\n",i); break; } } if(!find) printf("0\n"); } }

上一篇:黑马程序员————高新技术————类加载器
下一篇:PHP100 2012 压缩包解压密码

相关文章

相关评论