poj 2486（树形dp）

题意：给出一棵树，每个顶点有个权值，求解从顶点1出发经过不超过k条边，经过的顶点的权值和最大值。

思路：树形dp，dp[i][j][k]，以第i个顶点为根的子树，经过j条边状态为k时经过顶点的最大权值和.k=0表示回到点i，k=1表示不回到点i。

View Code

 1 #include<algorithm>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 #define N 110
 6 #define K 220
 7 int mx,k;
 8 vector<int> g[N];
 9 int dp[N][K][3],val[N];
10 void dfs(int u,int fa){
11     for(int i=0;i<=k;i++)
12     dp[u][i][0]=dp[u][i][1]=val[u];
13     for(int i=0;i<g[u].size();i++){
14         int v=g[u][i];
15         if(v==fa)continue;
16         dfs(v,u);
17         for(int j=k;j>=0;j--){
18             for(int f=0;f<=j;f++){
19                 dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-f][0]+dp[v][f][0]);
20                 dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-f][1]+dp[v][f][0]);
21                 dp[u][j+1][1]=max(dp[u][j+1][1],dp[u][j-f][0]+dp[v][f][1]);
22             }
23         }
24     }
25 }
26 int main(){
27     int n;
28     while(scanf("%d%d",&n,&k)!=EOF){
29         memset(dp,0,sizeof(dp));
30         memset(g,0,sizeof(g));
31         for(int i=1;i<=n;i++){
32             scanf("%d",&val[i]);
33         }
34         for(int i=1;i<n;i++){
35             int u,v;
36             scanf("%d%d",&u,&v);
37             g[u].push_back(v);
38             g[v].push_back(u);
39         }
40         dfs(1,0);
41         printf("%d\n",dp[1][k][1]);
42     }
43     return 0;
44 }