HDU 1561 ——The more, The Better(有依赖的树形DP)

前端之家收集整理的这篇文章主要介绍了HDU 1561 ——The more, The Better(有依赖的树形DP)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目分析:

攻占城堡所能获得的最多宝物,但是有个限制,要想攻占某个城堡前必须先攻占另一个城堡

思路:

建图,新建一个根节点为0,那么题目就变为要想取得子节点必须先取得它的父亲节点


今天为了解决这个问题,看了下背包九讲中的有依赖的背包,刷了道模板题。

大概思路是:要想取得附件必须先取主件,主件要么取,要么不取,取得话要怎么分配给附件,用01背包处理附件,然后再把每个主件分组背包

树形的依赖主要是附件是个集合,附件还有附件。森林的概念

根据DP的思想,我们先dfs到叶,01背包操作 即可。只是每次dfs后可以攻占的次数就减一

dp[i][j]表示以i为根攻占j次所能获得的最大宝物,则dp[i][1]=value[i]

这里的dp[i][j]是必须取i的意思,只有取了i,才能取i的子节点


  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #define M 10000
  6. using namespace std;
  7. struct pp{int v,w,next;}edge[M*2];int tot,root,head[M],n,m;
  8. inline void addedge(int u,int v,int w,int *h){edge[tot].v=v,edge[tot].w=w,edge[tot].next=h[u],h[u]=tot++;}
  9. int dp[210][210],vis[210],value[210];
  10. void dfs(int u,int c)
  11. {
  12. vis[u]=1;
  13. dp[u][1]=value[u];
  14. for(int i=head[u];i!=-1;i=edge[i].next){
  15. int v=edge[i].v;
  16. if(vis[v]) continue;
  17. dfs(v,c-1); //剩余所能攻占的次数减一
  18. for(int k=c;k>=0;--k){ //节点所能攻占的次数
  19. for(int j=0;j<k;++j){ //在所能攻占的次数里找到最优的
  20. dp[u][k]=max(dp[u][k],dp[u][k-j]+dp[v][j]); //01背包dp[i][j]=max(dp[i][j],dp[i][j-c]+w) //这里的w就是dp[v][j]
  21. }
  22. }
  23. }
  24. }
  25. int main()
  26. {
  27. while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
  28. memset(head,-1,sizeof head);
  29. for(int i=1;i<=n;++i){
  30. int u,w;
  31. scanf("%d%d",&u,&w);
  32. addedge(u,i,head);
  33. value[i]=w;
  34. }
  35. memset(dp,sizeof dp);
  36. memset(vis,sizeof vis);
  37. dfs(0,m+1);
  38. printf("%d\n",dp[0][m+1]);
  39. }
  40. return 0;
  41.  
  42. }

猜你在找的设计模式相关文章