POJ2486 Apple Tree（树形背包）

从每个节点u出发后有两种情况：回到u和不回到u。

dp数组设为三维，第一维是节点编号，第二维是从该节点开始走的步数，第三维1/0 表示是否回到该节点。

可以回到时：dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][1]);

不能回到时，分为两种情况：1.最终停在v子树上 2.最终停在其他子树上。

1.dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][1]+dp[v][t-1][0]);

2.dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][1]);

我们要枚举j和t，j代表的意义上文提到了，t则表示在从u到v这棵子树上走的步数，那么j-t就是在其他子树上走的步数，每棵子树v都要被枚举，由此分析可以得到上面的三种情况。

之所以叫树形背包是因为枚举j和t的部分类似于背包问题，其中j是要倒推的，因为每个节点的苹果树只能摘一次，摘完就没有了。（参考01背包的倒推思想）

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 using namespace std;

 5 const int M=210;

 6 int n,k,cnt;

 7 //dp[u][j][0]表示以u为根的树经过j步没有回到点u得到的最值

 8 //dp[u][j][1]表示以u为根的树经过j步回到点u得到的最值

 9 int dp[M][M][2],val[M],head[M];

10

11 struct edge{

12     int v,next;

13 }e[M<<1];

14

15 void init(){

16     memset(head,0,sizeof(head));

17     memset(dp,0,sizeof(dp));

18     cnt=0;

19 }

20

21 void add(int u,int v){

22     e[++cnt].next=head[u];

23     head[u]=cnt;

24     e[cnt].v=v;

25 }

26

27 void dfs(int u,int fa){

28     for(int i=0;i<=k;i++)

29         dp[u][i][0]=dp[u][i][1]=val[u];

30     for(int i=head[u];i;i=e[i].next){

31         int v=e[i].v;

32         if(v==fa) continue;

33         dfs(v,u);

34         for(int j=k;j>=1;j--)//树形背包

35             for(int t=1;t<=j;t++){

36                 dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][1]+dp[v][t-1][0]);

37                 if(t>=2) dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][1]);

38                 if(t>=2) dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][1]);

39             }

40     }

41 }

42

43 int main(){

44     int u,v;

45     while(~scanf("%d%d",&n,&k)){

46         init();

47         for(int i=1;i<=n;i++) scanf("%d",&val[i]);

48         for(int i=1;i<n;i++){

49             scanf("%d%d",&u,&v);

50             add(u,v);add(v,u);

51         }

52         dfs(1,-1);

53         printf("%d\n",max(dp[1][k][0],dp[1][k][1]));

54     }

55     return 0;

56 }

做这道题就是要从一个节点u分析，考虑他的情况（如本题回到与不回到），从而进一步分析每种可能的情况，得到方程。

POJ2486 Apple Tree（树形背包）的相关教程结束。