poj1947

这道题挺有意思的，标签是树形DP加背包。

一眼看过去其实状态挺好想的，显然根为x的子树取j个点可以形成最优子问题的解。

不过这道题的转移方程有点特殊，因为在不取某一个点的时候不是单纯的不去处理他就好了，而是也会对当前这个状态的值产生影响。

所以需要提前先取一个值表示取到这棵子树的时候不取这个点，然后再去比较取了这个点的值。

转移方程为：首先取一个tmp=dp[x][j]+1;表示以x为根的子树取了j个点，但是当前扫到这棵子树不取点

　　然后枚举这棵子树取的点数 tmp=min(tmp,dp[v][j-k]+dp[x][k]);

最后把tmp值赋给dp即可

因为标签是加了背包的嘛，所以实际做的时候应该能察觉到，这题枚举状态的时候也就是x为根的树取j个点的时候，j的枚举需要从大到小，以避免同一棵子树一直被取。

下附代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 const int INF=0X3f3f3f3f;
 6 int head[155],Next[305],to[305],tot=0,n,p,flag[155],dp[155][155];
 7 void add(int a,int b){
 8     Next[tot]=head[a],to[tot]=b;
 9     head[a]=tot++;
10 }
11 void dfs(int x,int pre){
12     dp[x][1]=0;
13     for (int i=head[x]; i!=-1; i=Next[i]){
14         int v=to[i];
15         if (v!=pre){
16             dfs(v,x);
17             for (int j=p; j>0; j--){
18                 int tmp=dp[x][j]+1;
19                 for (int k=1; k<j; k++){
20                     if (dp[v][j-k]+dp[x][k]<tmp){
21                         tmp=dp[v][j-k]+dp[x][k];
22                     }
23                 }
24                 dp[x][j]=tmp;
25             }
26         }
27     }
28 }
29 int main(){
30     while (scanf("%d%d",&n,&p)!=EOF){
31         tot=0;
32         memset(dp,INF,sizeof(dp));
33         memset(flag,0,sizeof(flag));
34         for (int i=1; i<=n; i++) head[i]=-1;
35         for (int i=1; i<n; i++){
36             int a,b;
37             scanf("%d%d",&a,&b);
38             flag[b]=1;
39             add(a,b);
40             add(b,a);
41         }
42         int root;
43         for (int i=1; i<=n; i++){
44             if (!flag[i]) {
45                 root=i;
46                 break;
47             }
48         }
49         dfs(root,-1);
50         int res=dp[root][p];
51         for (int i=1; i<=n; i++){
52             if (res>dp[i][p]+1)
53                 res=dp[i][p]+1;
54         }
55         printf("%d
",res);
56     }
57     return 0;
58 }

View Code