poj 1947 Rebuilding Roads 动态规划经典题目

/*
题目的意思是：一棵树n节点，要取任意一棵又k个节点的子树k<n 求最少需要切断的指数

  树形DP

题目链接：http://poj.org/problem?id=1947
  */

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int N=151;
const int MAX=1000000;

vector <short> tree[N];
bool hasfa[N];
short dp[N][N];
int n,p;

int min(int a,int b){
	return a<b?a:b;
}

void DFS(int root){
    for(int i=0;i<tree[root].size();i++){//如果是叶节点直接返回
        int so = tree[root][i];
        DFS(so); //不是叶节点时 先DFS其孩子
        for(int j=p;j>1;j--){//这个地方利用的是背包原理，刚开始有点迷惑，请教了大圣后 又自己调试了一遍观察了所有值的变化后才明白
            for(int k=1;k<j;k++){//感觉这里可以优化                         //父亲承担n个某孩子承担k个时，父与次子之间相连但是却按不练计算  所以要在减去多算的这两次
                dp[root][j] = min(dp[root][j],dp[root][j-k] + dp[so][k] -2);//即这里之所以减2 是因为假设1是2的父亲k=1,j=2时，当dp[1][2]=dp[1][1]+dp[2][1]
            }                                                             //这时就会发现dp[1][1]把1-2之间断开了，dp[2][1]计算时也把1-2断开了，其实这里
        }                                                                 //dp[1][2]也就是1节点保留一个节点连接上2节点保留一个节点所以1-2之间不该断所以多断了两次需要减去2
    }
}

int main(){
	int i;
    scanf("%d%d",&n,&p);
    memset(hasfa,0,sizeof(hasfa));
    int pa,so;
    for(i = 1;i < n;i++){
        scanf("%d%d",&pa,&so);
        tree[pa].push_back(so);
        hasfa[so]=true;
    }
    int root = 1;
    for(i=1;i<=n;i++){
		if(!hasfa[i]){
			root=i;
			break;
		}
	}
    for(i = 1;i <= n;i++){
        dp[i][1]=tree[i].size()+1;//每个节点当只保留一个节点时即dp[i][1]=i的孩子总数加上1  这里实说节点要断开所以与孩子相连的路以及与父母相连的路
        for(int j=2;j<=n;j++)
            dp[i][j] = MAX;
    }
    DFS(root);
    dp[root][p]--;           //因为根节点也计算着断开与父母的节点  但实际上根节点没有父母所以要减1
    int mi = MAX;
    for(i = 1;i <= n;i++){
        mi = min(mi,dp[i][p]);//在所有节点保留p个点时需要的断路条数中选择最小的即是所求解
    }
    printf("%d\n",mi);
    return 0;
}