首页 > 代码库 > POJ 1947 （树形DP+背包)
POJ 1947 （树形DP+背包)
题目链接: http://poj.org/problem?id=1947
题目大意：树中各点都由一条边连接。问要弄出个含有m个点的（子）树，至少需要截去多少条边。
解题思路：
设dp[i][j]为i总根（注意是当前点为总根，不再考虑其父亲，这题是要在原来的树里面切出一个树），留下j个点截去的最少的边。
首先dp[i][1]=子结点数量，即只留下根，要把所有与子节点的边给截掉。
对于dp[i][2~m]：如果取子结点，则dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]-1)
这里的-1比较巧妙，用的是逆向思维。如果硬要把子树接上去的话，则就被截取边就得少一条，则-1。
至于为什么是dp[i][j-k]+dp[t][k]，这里理解成根与儿子共同分一个j，所以取和。
最后的DP的结果比较难想：
ans=min(dp[1][m],dp[2~n][m]+1)
即如果以1为总根，则dp[1][m]就是结果。
否则对于其它点，要使其为总根，则必须切断其与父亲的边，所以结果+1。
#include "cstdio"#include "iostream"#include "cstring"using namespace std;#define maxn 155#define inf 0x3f3f3f3fint n,m,u,v,head[maxn],son[maxn],tol;int dp[maxn][maxn];struct Edge{ int next,to;}e[maxn];void addedge(int u,int v){ e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}int dfs(int root){ dp[root][1]=son[root]; int i=root; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; dfs(t); for(int j=m;j>=1;j--) for(int k=1;k<=j-1;k++) dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]-1); }}int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); memset(dp,0x3f,sizeof(dp)); memset(head,-1,sizeof(head)); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); son[u]++; addedge(u,v); } dfs(1); int ans=inf; for(int i=1;i<=n;i++) { if(i==1) ans=min(ans,dp[i][m]); else ans=min(dp[i][m]+1,ans); } printf("%d\n",ans);}
| 13544792 | neopenx | 1947 | Accepted | 252K | 0MS | C++ | 1010B | 2014-10-19 15:40:17 |
POJ 1947 （树形DP+背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。