題干：

Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at one node. She can eat up all the apples in the nodes she reaches. HX is a kind guy. He knows that eating too many can make the lovely girl become fat. So he doesn’t allow Wshxzt to go more than K steps in the tree. It costs one step when she goes from one node to another adjacent node. Wshxzt likes apple very much. So she wants to eat as many as she can. Can you tell how many apples she can eat in at most K steps.

Input

There are several test cases in the input?
Each test case contains three parts.?
The first part is two numbers N K, whose meanings we have talked about just now. We denote the nodes by 1 2 ... N. Since it is a tree, each node can reach any other in only one route. (1<=N<=100, 0<=K<=200)?
The second part contains N integers (All integers are nonnegative and not bigger than 1000). The ith number is the amount of apples in Node i.?
The third part contains N-1 line. There are two numbers A,B in each line, meaning that Node A and Node B are adjacent.?
Input will be ended by the end of file.?

Note: Wshxzt starts at Node 1.

Output

For each test case, output the maximal numbers of apples Wshxzt can eat at a line.

Sample Input

2 1 0 11 1 2 3 2 0 1 2 1 2 1 3

Sample Output

11 2

題目大意：

一顆樹，n個點（1-n），n-1條邊，每個點上有一個權值，求從1出發，走k步，最多能遍歷到的權值。

多組數據?
第一行兩個整數N,K 1<=N<=100,0<=k<=200?
第二行N個整數,0<=x<=1000表示每個節點中蘋果的數量?
最后N-1行描述兩個點相連

解題報告：

每次先對子節點做一遍01背包

dp[i][j]表示在i節點走j步可以得到的最大權值，因為可以發現，答案的數目只跟走的步數有關，而跟這些步數是怎么走的無關，所以設置狀態為此。

這里注意的就是有時要走回頭路

那么dp[i][j]要加一維，回到根節點或不回到跟節點，加上這個狀態是為了方便后去走到其他的兒子節點。

0不回來1回來的話

dp[rt][j][0]=max(dp[rt][j][0],dp[rt][j-k][1]+dp[v][k-1][0]);

不回來的狀態 為? ? 其他節點回來并且當前節點不回來

dp[rt][j][0]=max(dp[rt][j][0],dp[rt][j-k][0]+dp[v][k-2][1]);

不回來的狀態 為? ??其他節點不回來 當前節點回來

dp[rt][j][1]=max(dp[rt][j][1],dp[rt][j-k][1]+dp[v][k-2][1]);

回來的狀態 為? ? 其他節點都要回來，并且當前兒子也要回來。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 205 + 5; vector<int> vv[MAX]; int n,m; int dp[MAX][MAX][2],a[MAX]; void dfs(int cur,int rt) {int up = vv[cur].size();for(int i = 0; i<=m; i++) dp[cur][i][0] = dp[cur][i][1] = a[cur];for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);for(int j=m; j>=1; j--) {for(int k=1; k<=j; k++) {dp[cur][j][0]=max(dp[cur][j][0],dp[cur][j-k][1]+dp[v][k-1][0]);dp[cur][j][0]=max(dp[cur][j][0],dp[cur][j-k][0]+dp[v][k-2][1]);dp[cur][j][1]=max(dp[cur][j][1],dp[cur][j-k][1]+dp[v][k-2][1]);}}} } int main() {while(~scanf("%d%d",&n,&m)) {for(int i = 1; i<=n; i++) scanf("%d",a+i),vv[i].clear();memset(dp,0,sizeof dp);for(int a,b,i = 1; i<=n-1; i++) {scanf("%d%d",&a,&b);vv[a].pb(b);vv[b].pb(a);}dfs(1,-1);printf("%d\n",max(dp[1][m][0],dp[1][m][1]));}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 2486】Apple Tree （树形背包，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。