http://acm.pku.edu.cn/JudgeOnline/problem?id=2486题目给定一棵有N个节点的无向树，每个节点有个权值，当第一次到达某节点时，可以获得该权值。从节点1出发，至多走K步，每步能走到当前节点的任意邻接点，要求能获得的权值和的最大值。N<=100，K<=200。
对DFS树中某节点，从它开始，可以进入任意子树获得一定权值后返回该点，也可以不返回（这意味着终止于子树里）。
这样可以设：
dp[i][j][0]: 以i为根, 以至多j步访问该子树并返回原地的最大收获
dp[i][j][1]: 以i为根, 以至多j步访问该子树且不需要返回时的最大收获
那么，dp[1][K][1]就是最终结果。
显然这两个值的更新过程可以用深搜DP。
考虑以r为根的DFS子树，则dp[r][j][0..1]的更新，实际上是以步数j为背包容量，以所有子树为物品的背包问题。
于是可以再设：
dps[i][j][0]：前i棵子树，最大步数j，需要返回时的最大收获
dps[i][j][1]：前i棵子树，最大步数j，不需要返回时的最大收获
DFS完一棵子树就做一次背包，状态复杂度O(K*子树数），转移复杂度O(K)
整体复杂度为O(N*K^2)
代码如下：
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 using namespace std;
7
8 struct EDGE{
9 int v,e;
10 }edg[330];
11 int se, gg[110];
12 bool vis[110];
13 int w[110],dp[110][220][2];
14 int N,K;
15
16 inline void addedge(int u, int v){
17 edg[se].v = v;
18 edg[se].e = gg[u];
19 gg[u] = se++;
20 }
21
22 bool input(){
23 int i,j,k;
24 if(scanf("%d %d",&N,&K)==EOF)
25 return false;
26 se = 2;
27 memset(gg,0,sizeof(gg));
28 for(i=1; i<=N; i++)
29 scanf("%d",&w[i]);
30 for(i=1; i<=N-1; i++){
31 scanf("%d %d",&j,&k);
32 addedge(j,k);
33 addedge(k,j);
34 }
35 }
36
37 void dfs(int r){
38 int i,j,k,u,v,e;
39 int mx0, mx1;
40 vis[r] = true;
41 for(e=gg[r]; e>0; e=edg[e].e){
42 u = edg[e].v;
43 if(!vis[u]){
44 dfs(u);
45 for(k=K; k>=0; k--){
46 mx0 = mx1 = w[r];
47 for(j=0; j<=k-1; j++){
48 if(k>=2 && j<=k-2){
49 mx0 = max(mx0, dp[r][j][0]+dp[u][k-2-j][0]);
50 mx1 = max(mx1, dp[r][j][1]+dp[u][k-2-j][0]);
51 }
52 if(k>=1 && j<=k-1){
53 mx1 = max(mx1, dp[r][j][0]+dp[u][k-1-j][1]);
54 }
55 }
56 dp[r][k][0] = max(dp[r][k][0], mx0);
57 dp[r][k][1] = max(dp[r][k][1], mx1);
58 }
59 }
60 }
61 }
62
63 void solve(){
64 int i,j,k;
65 for(i=1; i<=N; i++)
66 for(j=0; j<=K; j++)
67 dp[i][j][0] = dp[i][j][1] = w[i];
68 memset(vis,false,sizeof(vis));
69 dfs(1);
70 printf("%d\n", max(dp[1][K][0],dp[1][K][1]) );
71 }
72
73 int main(){
74 while(input()){
75 solve();
76 }
77 return 0;
78 }
posted on 2009-06-03 13:09
wolf5x 阅读(702)
评论(2) 编辑 收藏 引用 所属分类:
acm_icpc