POJ 1947 树形DP入门题

本文主要是介绍POJ 1947 树形DP入门题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出N个点，N-1个关系，建出树形图，问最少减去几个边能得到节点数为P的树。典型树形DP题

dp[cur][j] :记录cur结点，要得到一棵j个节点的子树去掉的最少边数

转移方程用的背包的思想

对当前树的每一个子树进行计算

砍掉此子树：   dp[cur][j]=dp[cur][j]+1;

不砍掉：           for (l=0;l<=j;l++)  dp[cur][j]=Min(dp[cur][j],dp[cur][l]+dp[next][j-l]); 枚举从该树中留l个节点其他由新进子树得到的方案的代价 dp[cur][l]+dp[next][j-l]；

#include "stdio.h"
#include "vector"
#include "math.h"
#include "string.h"
int inf=0x3f3f3f3f;
using namespace std;struct node
{int fa;vector<int>child;
}data[160];int dp[160][160];
int p;int Min(int a,int b)
{if (a<b) return a; else return b;
}void dfs(int cur)
{int next,i,j,l;dp[cur][1]=0;for (i=0;i<data[cur].child.size();i++){next=data[cur].child[i];dfs(next);for (j=p;j>=0;j--){dp[cur][j]=dp[cur][j]+1;for (l=0;l<=j;l++)dp[cur][j]=Min(dp[cur][j],dp[cur][l]+dp[next][j-l]);}}
}
int main()
{int n,a,b,i,root,ans;while (scanf("%d%d",&n,&p)!=EOF){memset(dp,inf,sizeof(dp));memset(data,0,sizeof(data));for (i=1;i<n;i++){scanf("%d%d",&a,&b);data[b].fa=a;data[a].child.push_back(b);}for (i=1;i<=n;i++)if (data[i].fa==0){root=i;break;}dfs(root);ans=dp[root][p];for (i=1;i<=n;i++)ans=Min(ans,dp[i][p]+1);printf("%d\n",ans);}return 0;
}

这篇关于POJ 1947 树形DP入门题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---