POJ 1947 - Rebuilding Roads 树型DP(泛化背包转移)..
DP poj 背包 转移 .. 泛化 树型
2023-09-27 14:22:42 时间
dp[x][y]表示以x为根的子树要变成有y个点..最少需要减去的边树... 最终ans=max(dp[i][P]+t) < i=(1,n) , t = i是否为整棵树的根 >
更新的时候分为两种情况..一种是要从其这个孩子转移过来...枚举做01背包..更新出每个状态的最小值..或者说直接砍掉这个孩子..那么只需将所有的状态多加个砍边...
这里的枚举做01背包..意思是由于叶子节点要放多少进去不确定..叶子节点要放的大小以及本节点的空间都在枚举更新...这种概念就是泛化背包..本质上是01背包.做多次01背包
注意到枚举空间的顺序.这样能保证更新的时候不出现混乱....
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<set> #include<ctime> #include<algorithm> #include<queue> #include<cmath> #include<map> #define oo 100000007 #define ll long long #define pi acos(-1.0) #define MAXN 155 using namespace std; vector<int> Tree[MAXN]; int dp[MAXN][MAXN],N,P,ans; bool root[MAXN]; int dfs(int x) { int i,j,y,m=Tree[x].size(),num=1,t,update; for (i=0;i<=P;i++) dp[x][i]=oo; dp[x][1]=0; for (i=0;i<m;i++) { y=Tree[x][i]; num+=dfs(y); for (t=P;t>=1;t--) { update=dp[x][t]+1; for (j=1;j<=t;j++) update=min(update,dp[x][t-j]+dp[y][j]); dp[x][t]=update; } //泛化背包转移 } t=0; if (!root[x]) t++; if (dp[x][P]!=-1) ans=min(dp[x][P]+t,ans); return num; } int main() { int i; while (~scanf("%d%d",&N,&P)) { for (i=1;i<=N;i++) Tree[i].clear(); memset(root,true,sizeof(root)); for (i=1;i<N;i++) { int x,y; scanf("%d%d",&x,&y); Tree[x].push_back(y); root[y]=false; } for (i=1;i<=N;i++) if (root[i]) break; ans=oo; dfs(i); printf("%d\n",ans); } return 0; }
相关文章
- poj 2385Apple Catching(简单dp)
- 【UVa】Jump(dp)
- 【BZOJ】2017: [Usaco2009 Nov]硬币游戏(dp+神题+博弈论)
- POJ 1836 Alignment (双向DP)
- POJ 3691 DNA repair (DP+AC自动机)
- POJ 1655 - Balancing Act 树型DP
- POJ 3666 Making the Grade [DP]
- Discrete Centrifugal Jumps CodeForces - 1407D 单调栈+dp
- HDU - 1789 dp
- POJ 1625 Censored!(AC自动机+DP+高精度)
- UVA 1401 - Remember the Word(Trie+DP)
- poj 2151 Check the difficulty of problems(概率DP)
- ZOJ 3329 One Person Game 带环的概率DP
- HDU 1025 Constructing Roads In JGShining's Kingdom (DP)
- 树形DP 统计树中长度为K的路径数量——Distance in Tree
- 【luogu P7529】Permutation G(几何)(数学)(DP)
- 【UR #7 C】水题走四方(DP)
- 【POJ 3311】Hie with the Pie(状压DP)
- 【ybt高效进阶5-6-5】【luogu P3957】跳房子(二分)(单调队列优化DP)