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]]<ans-1) ans=dp[x][p-n+sum[x]]+1;
　 我这里的P为了处理方便,先转化成了n-p..那么n-sum[x]..代表以x为根的子树独立出去..会抛掉其他的n-sum[x]点(sum[x]为x为根的子数的节点总数)..那么以x为根的子树还要剪p-(n-sum[x])条边才能满足条件..并且还要将此点与其父亲的边剪掉..所以对于x为根的满足条件的子树,最少的剪枝数为dp[x][p-n+sum[x]]+1

Program:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;  
int n,p,i,x,y,father[160],sum[160],dp[160][160],head,leaf[160],ans;
queue<int> 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;i<n;i++) 
      {
            scanf("%d%d",&x,&y);
            father[y]=x;
            leaf[x]++;
      } 
      memset(dp,0x7F,sizeof(dp)); 
      while (!myqueue.empty()) myqueue.pop();
      for (i=1;i<=n;i++) 
      {
            dp[i][0]=0;
            if (!leaf[i]) myqueue.push(i);
            sum[i]=1;
      }
      p=n-p;
      ans=10000;
      while (!myqueue.empty())
      {
            x=myqueue.front();
            myqueue.pop();
            y=father[x];
            if (!y) break;
            sum[y]+=sum[x];
            if (dp[x][p-n+sum[x]]<ans-1) ans=dp[x][p-n+sum[x]]+1;
            for (i=0;i<=sum[y]-sum[x];i++)
               if (dp[y][i]<1000 && dp[y][i+sum[x]]-1>dp[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]<ans) ans=dp[x][p];
      printf("%d\n",ans);
      return 0;
}