POJ-1947 简单的树型DP,但要考虑完全

POJ-1947 简单的树型DP,但要考虑完全

题目的意思是说给出一个N个节点的树,问最少要剪枝多少才能得到点数为P的子树...

我的做法是从叶子节点按Top顺序更新到根节点,用dp[k][i]来表示保留k点并对其子树剪枝,去掉i个点所需的最少剪枝数...那么一路做到根节点,答案应该是dp[head][n-p]..

但是...这样会WA..因为没有注意..题目之说是点数为P的子树..并没说要包括根节点..譬如说样例输入给的树,若说保留1个点...答案应该是1..切出一个叶子节点就可以了..为了解决这个问题..在dp更新新时加个判断就可以了..

if (dp[x][p-n+sum[x]]

Program:

#include#include#include#include#include#includeusing namespace std; int n,p,i,x,y,father[160],sum[160],dp[160][160],head,leaf[160],ans;queue myqueue;int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); memset(father,0,sizeof(father)); memset(leaf,0,sizeof(leaf)); scanf("%d%d",&n,&p); for (i=1;idp[y][i]) dp[y][i+sum[x]]=dp[y][i]+1; for (i=1;i<=sum[x];i++) if (dp[y][i]>dp[x][i]) dp[y][i]=dp[x][i]; leaf[y]--; if (!leaf[y]) myqueue.push(y); } if (dp[x][p]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。