http://poj.org/problem?id=2486
典型的回溯题目：特别是状态方程用三维的来标记是否要走回路。
题意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值思路：
树形dp，比较经典的一个树形dp。首先很容易就可以想到用dp[root][k]表示以root为根的子树中最多走k时所能获得的最多苹果数，接下去我们很习惯地会想到将k步在root的所有子结点中分配，也就是进行一次背包，就可以得出此时状态的最优解了，但是这里还有一个问题，那就是在进行背包的时候，对于某个孩子son走完之后是否回到根结点会对后面是否还能分配有影响，为了解决这个问题，我们只需要在状态中增加一维就可以了，用dp[root][k][0]表示在子树root中最多走k步，最后还是回到root处的最大值，dp[root][k][1]表示在子树root中最多走k步，最后不回到root处的最大值。由此就可以得出状态转移方程了：
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6836 | Accepted: 2268 |
Description
Input
Output
Sample Input
2 1 0 11 1 2 3 2 0 1 2 1 2 1 3
Sample Output
11 2
dp[root][j][0] = MAX (dp[root][j][0] , dp[root][j-k][0] + dp[son][k-2][0]);//从s出发，要回到s，需要多走两步s-t,t-s,分配给t子树k步，其他子树j-k步，都返回
dp[root][j]][1] = MAX( dp[root][j][1] , dp[root][j-k][0] + dp[son][k-1][1]) ;//先遍历s的其他子树，回到s，遍历t子树，在当前子树t不返回，多走一步
dp[root][j][1] = MAX (dp[root][j][1] , dp[root][j-k][1] + dp[son][k-2][0]);//不回到s（去s的其他子树），在t子树返回，同样有多出两步
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 |
//（1）dp[i][j+2][0] = max(dp[i][j+2][0], dp[i][j-k][0]+dp[son][k][0]);//（2）dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j-k][0]+dp[son][k][1]); 人留在i的子节点son的子树中//（3）dp[i][j+2][1] = max(dp[i][j+2][1], dp[i][j-k][1]+dp[son][k][0]); 人留在不是son的i的子节点的子树中#include<iostream>#include<cstring>#include<cstdio>using
namespace std;int dp[300][300][3],head[300],vis[300],w[300];int len,n,k;struct
node{ int
now,next;} tree[505];int
max(int
x,int y){ if(x>y) return
x; else return
y;}void
add(int
x,int y){ tree[len].now = y; tree[len].next = head[x]; head[x] = len++;}void
dfs(int
root,int
mark){ int
j,son,t,i; for(i=0;i<=k;i++) dp[root][i][0] = dp[root][i][1] = w[root]; for(i=head[root];i!=-1;i=tree[i].next) { printf("i=%d\n",i); son = tree[i].now; if(son == mark)//已经加了，就不要加，不然就死循环。 continue; dfs(son,root); for(j = k; j>=1; j--) { for(t = 1; t<=j; t++) { dp[root][j][1]=max(dp[root][j][1],dp[root][j-t][1]+dp[son][t-2][1]); dp[root][j][0]=max(dp[root][j][0],dp[root][j-t][1]+dp[son][t-1][0]); dp[root][j][0]=max(dp[root][j][0],dp[root][j-t][0]+dp[son][t-2][1]); } } }}int
main(){ int
i,a,b,j; while(~scanf("%d%d",&n,&k)) { len=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); for(i = 1; i<=n; i++) { scanf("%d",&w[i]); } for(i=1;i<n;i++) { cin>>a>>b; add(a,b); add(b,a); } dfs(1,0); printf("%d\n",max(dp[1][k][0],dp[1][k][1])); } return
0;} |
poj 2408 Apple Tree,布布扣,bubuko.com
原文：http://www.cnblogs.com/cancangood/p/3641458.html