首页 > 代码库 > HDU 1011 (树形DP+背包）
HDU 1011 (树形DP+背包）
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1011
题目大意：树上取点，先取父亲，再取儿子。每个点，权为w，花费为cost，给定m消费总额，求最大权和。
解题思路：
树形背包模板题。首先建一个无向图。
每个点的cost=(bug[root]+19)/20，即虫子数不满20也要派一个人。
用dp[i][j]表示以i为根的子树中，花费为j的最大权和。
转移方程：dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k])，其中t为儿子之一，k为分配给儿子的cost。
采用dfs对每个root进行DP。
每次dfs的时候，先对cost~m进行初始化，值为w[root]，表示只取父亲的情况。
之后对每个儿子进行dfs，每次都是两个for循环。
for(m...j...cost)
for(1...k....j-cost) //儿子最多分配j-cost
则最后结果就是dp[1][m]，其中1是总root点。
注意本题m可以等于0，所以在全部读入数据之后对0特判输出0，否则再dfs。
#include "cstdio"#include "vector"#include "cstring"using namespace std;#define maxn 500int bug[maxn],w[maxn],head[maxn],n,m,u,v,tol;struct Edge{ int to,next;}e[maxn*2];bool vis[maxn];int dp[maxn][maxn];void addedge(int u,int v){ e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}void dfs(int root,int pre){ int i=root,cost=(bug[root]+19)/20; for(int i=cost;i<=m;i++) dp[root][i]=w[root]; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; if(t==pre) continue; dfs(t,root); for(int j=m;j>=cost;j--) for(int k=1;k<=j-cost;k++) dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]); }}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)&&n>0) { memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); tol=0; for(int i=1;i<=n;i++) scanf("%d%d",&bug[i],&w[i]); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } if(m==0) {printf("0\n");continue;} dfs(1,1); printf("%d\n",dp[1][m]); } return 0;}
| 11488265 | 2014-08-19 12:44:12 | Accepted | 1011 | 62MS | 1280K | 1508 B | C++ | Physcal |
HDU 1011 (树形DP+背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。