poj 2486 Apple Tree(樹形DP 狀态方程有點難想)

Apple Tree

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 9808	Accepted: 3260

Description

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
      

11
2
      

POJ Contest,Author:magicpig@ZSU

/*
給你一顆蘋果樹，每個節點都有相應的蘋果樹，讓你求從結點1開始走最多走k步，能吃到的最多蘋果數
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#define N 220
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
    int to;
    node (int TO){to=TO;};
};
int n,k;
int dp[N][N][2];//dp[u][k]表示以u為根結點，走到k步時,返不傳回根節點的最多擷取多少蘋果
int val[N];//盛放每個點的蘋果數
vector<node>edge[N];
/*
（1）不能用記憶化搜尋因為可能不是最後一步取到的最大值

（2）不是一條路徑走到底能吃多少蘋果，這樣周遊，因為雖然走過一個地方就把這個地方的蘋果吃光，但是如果走完一條路徑的時候還有餘下的步數可以傳回
再接着吃别的路徑的

*/
void dfs(int u,int p)//這一步，上一部，還剩多少步；
{
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i].to;
        if(v==p) continue;
        dfs(v,u);
        for(int j=k;j>=1;j--)
        {
            for(int k=1;k<=j;k++)
            {
                dp[u][j][0]=max(dp[u][j][0],dp[u][j-k][1]+dp[v][k-1][0]);
                //從u到v回到u，在v中周遊的時候不回來
                //不傳回根節點的，頂點u隻用j-k步，剩下的給v，因為由u到v要耗費一步，是以在v點的時候最多隻能走k步
                dp[u][j][0]=max(dp[u][j][0],dp[u][j-k][0]+dp[v][k-2][1]);
                //從u點到v點，然後v點回來
                //不傳回根節點的，頂點u隻用j-k步，剩下的給v，因為由u到v，再由v到u要耗費兩步，是以在v點的時候最多隻能走k步
                dp[u][j][1]=max(dp[u][j][1],dp[u][j-k][1]+dp[v][k-2][1]);
                //從u點到v點，然後v點中周遊回到v，再回到u
                //傳回根節點的，頂點隻用j-k步，剩下的給v，因為由u到v，再由v到u要耗費兩步，是以在v點的時候最多隻能走k步
            }    
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            for(int j=0;j<=k;j++)
                dp[i][j][1]=dp[i][j][0]=val[i];//初始化
            edge[i].clear();
            //cout<<val[i]<<" ";
        }    
        //cout<<endl;
        int a,b;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        dfs(1,0);
        printf("%d\n",max(dp[1][k][1],dp[1][k][0]));
    }
    return 0;
}      

我每天都在努力,隻是想證明我是認真的活着.