首页 > 代码库 > HDU 1561 (树形DP+背包)
HDU 1561 (树形DP+背包)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1561
题目大意：从树根开始取点。最多取m个点，问最大价值。
解题思路：
cost=1的树形背包。
有个虚根0，取这个虚根也要cost，所以最后的结果是dp[0][m+1]。
本题是cost=1的特殊背包问题，在两个for循环上有一个优化。
for(f+1...j....cost)
for(1....k...j-cost)
其中f为当前已经dfs子结点个数。之所以+1，是因为根要预留一个空间。
f+=dfs(t)，dfs(t)返回的是子点t的f+1。
其实可以直接把f+1写成m+1, 不过要多好多次没必要的循环。
#include "cstdio"#include "vector"#include "cstring"using namespace std;#define maxn 205int n,m,u,dp[maxn][maxn],w[maxn],head[maxn],tol;struct Edge{ int to,next;}e[maxn];void addedge(int u,int v){ e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}int dfs(int root){ int i=root,cost=1,f=0; for(int i=cost;i<=m;i++) dp[root][i]=w[root]; if(head[root]==-1) return 1; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; f+=dfs(t); for(int j=f+1;j>=1;j--) { for(int k=1;k<=j-cost;k++) { dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]); } } } return f+1;}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)&&n&&m) { memset(head,-1,sizeof(head)); tol=0; for(int i=1;i<=n;i++) { scanf("%d%d",&u,&w[i]); addedge(u,i); } dfs(0); printf("%d\n",dp[0][m+1]); memset(dp,0,sizeof(dp)); }}
| 11910646 | 2014-10-19 14:01:53 | Accepted | 1561 | 0MS | 400K | 1099 B | C++ | Physcal |
HDU 1561 (树形DP+背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。