首页 > 代码库 > 树形dp入门练习（hdu1011+hdu1061）
树形dp入门练习（hdu1011+hdu1061）
hdu1011 和 hdu1561类似，给定每个节点的花费以及价值，并且子节点必须在父亲节点取到以后才可以被取到
相当于是在树上进行的01背包
dp时考虑每一个子树 root和它的每一个儿子，状态转移方程为
dp[root][j]=max(dp[root][j],dp[root][j-k]+dp[ son[p] ][ k ])
以下为ac代码
hdu1011：这题有一个小坑，最后必须要剩余至少一个人。。开始没考虑到，一直wa
#include<stdio.h>#include<iostream>#include<stdlib.h>#include<math.h>#include<ctype.h>#include<algorithm>#include<string>#include<string.h>#include<queue>#define mod 1000000007#define MAX 100000000using namespace std;int t,n,m,p,k,tt;int map[105][105];int dp[105][105];int a[105];int w[105];int vi[105];void dfs(int s){ vi[s]=1; int cost=(w[s]+19)/20; for(int i=cost;i<=m;i++) dp[s][i]=a[s]; for(int i=1;i<=n;i++) { if(!map[s][i]) continue; if(vi[i]) continue; dfs(i); for(int k=m;k>=cost;k--) for(int j=1;j+cost<=k;j++) dp[s][k]=max(dp[s][k],dp[s][k-j]+dp[i][j]); }}int main(){ while(scanf("%d%d",&n,&m)&&(n!=-1||m!=-1)) { int x,y; memset(map,0,sizeof(map)); memset(dp,0,sizeof(dp)); memset(vi,0,sizeof(vi)); a[0]=0; for(int i=1;i<=n;i++) { scanf("%d%d",w+i,a+i); } for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); map[x][y]=1; map[y][x]=1; } if(m==0) { puts("0"); continue; } dfs(1); printf("%d\n",dp[1][m]); } return 0;}
hdu 1561
#include<stdio.h>#include<iostream>#include<stdlib.h>#include<math.h>#include<ctype.h>#include<algorithm>#include<string>#include<string.h>#include<queue>#define mod 1000000007#define MAX 100000000using namespace std;int t,n,m,p,k,tt;int map[201][201];int dp[201][201];int a[201];void dfs(int s){ for(int j=1;j<=m+1;j++) dp[s][j]=a[s]; for(int i=1;i<=n;i++) { if(!map[s][i]) continue; dfs(i); for(int k=m+1;k>=1;k--) for(int j=0;j+1<=k;j++) dp[s][k]=max(dp[s][k],dp[s][k-j]+dp[i][j]); }}int main(){ while(scanf("%d%d",&n,&m)&&(n+m)) { memset(map,0,sizeof(map)); memset(dp,0,sizeof(dp)); int x; a[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&x); map[x][i]=1; scanf("%d",a+i); } dfs(0); printf("%d\n",dp[0][m+1]); } return 0;}
树形dp入门练习（hdu1011+hdu1061）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。