poj1947 树形DP

  应该是属于偏简单的一类树形DP了。思路很明确，dp[ i ][ n ]表示以i为根节点的子树中取n个点的子树所需的最小代价（所需删的边数）。那么对于一个节点 i 有dp[ i ][ 1 ] = 0，那么对于其儿子节点 j  就有大致两种情况了：①根本不取 j 子树上的，此时代价为dp[ i ][ n ]+1（即删除 i 到 j 的这条边）；②取 j 子树上的 k 个节点那么代价就是dp[ i ][ n - k] + dp[ j ][ k ]。我们每次在这两者之间取最小值就是了。

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;

int head[200],flag[200];
int N,P;
int dp[200][200];
struct NODE
{
    int to,next;
}edge[5000];

void dfs(int x)
{
    int i,j,k,to,temp;
    for(i=0;i<=P;i++) dp[x][i]=1000000;
    dp[x][1]=0;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].to;
        dfs(to);
        for(j=P;j>0;j--)
        {
            temp=dp[x][j]+1;
            for(k=1;k<j;k++) temp=min(temp,dp[x][j-k]+dp[to][k]);
            dp[x][j]=temp;
        }
    }
    return;
}

int main()
{
    while(~scanf("%d %d",&N,&P))
    {
        int i;
        int a,b;
        memset(head,-1,sizeof(head));
        memset(flag,0,sizeof(flag));
        for(i=1;i<N;i++)
        {
            scanf("%d %d",&a,&b);
            flag[b]++;
            edge[i].to=b,edge[i].next=head[a],head[a]=i;
        }
        int root;
        for(i=1;i<=N;i++) if(!flag[i]) {root=i;break;}
        dfs(root);
        int ans=dp[root][P];
        for(i=1;i<=N;i++) ans=min(ans,dp[i][P]+1);
        printf("%d\n",ans);
    }
}

poj1947 树形DP,布布扣,bubuko.com

poj1947 树形DP

原文：http://blog.csdn.net/alone_l/article/details/20316517