http://acm.pku.edu.cn/JudgeOnline/problem?id=2486題目給定一棵有N個(gè)節(jié)點(diǎn)的無向樹，每個(gè)節(jié)點(diǎn)有個(gè)權(quán)值，當(dāng)?shù)谝淮蔚竭_(dá)某節(jié)點(diǎn)時(shí)，可以獲得該權(quán)值。從節(jié)點(diǎn)1出發(fā)，至多走K步，每步能走到當(dāng)前節(jié)點(diǎn)的任意鄰接點(diǎn)，要求能獲得的權(quán)值和的最大值。N<=100，K<=200。
對DFS樹中某節(jié)點(diǎn)，從它開始，可以進(jìn)入任意子樹獲得一定權(quán)值后返回該點(diǎn)，也可以不返回（這意味著終止于子樹里）。
這樣可以設(shè)：
dp[i][j][0]: 以i為根, 以至多j步訪問該子樹并返回原地的最大收獲
dp[i][j][1]: 以i為根, 以至多j步訪問該子樹且不需要返回時(shí)的最大收獲
那么，dp[1][K][1]就是最終結(jié)果。
顯然這兩個(gè)值的更新過程可以用深搜DP。
考慮以r為根的DFS子樹，則dp[r][j][0..1]的更新，實(shí)際上是以步數(shù)j為背包容量，以所有子樹為物品的背包問題。
于是可以再設(shè)：
dps[i][j][0]：前i棵子樹，最大步數(shù)j，需要返回時(shí)的最大收獲
dps[i][j][1]：前i棵子樹，最大步數(shù)j，不需要返回時(shí)的最大收獲
DFS完一棵子樹就做一次背包，狀態(tài)復(fù)雜度O(K*子樹數(shù)），轉(zhuǎn)移復(fù)雜度O(K)
整體復(fù)雜度為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 閱讀(748)
評論(2) 編輯 收藏 引用 所屬分類:
acm_icpc