POJ2486 나무 위 가방 누드 문제

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
Sample Output 11 2
이 문제는 주로 한 걸음의 분배 문제에 있다. 따라서 상태 이동 방정식은 비교적 이해하기 어렵다.
K보를 주었으니 너는 자나무에 들어갈 수 있을 뿐만 아니라 자나무에서 나올 수도 있다.그러나 같은 노드는 처음 걸어올 때만 그의 권한을 얻는다.
다른 때는 다리 하나만 작용할 수 있다.
매번 dfs에서 대응하는 모든 하위 트리는 독립적이다
그래서 다른 나무는 모든 걸음걸이가 q-w 안에 있어요.
그리고 그의 컨디션이 높은 단계에서 낮은 단계로 이동하는 이유는 그의 컨디션이 자신과 관련이 있기 때문이다. 만약에 그가 작은 단계에서 큰 단계로 이동하면 dp[gen][q+2][0] 이 부분은 끊임없이 커진다. 마치 완전한 배낭과 비슷한 것이다.
그런데 실제로는...이 나무의 노드마다 한 번만 뽑을 수 있다는 생각이 듭니다.
따라서 이 상태의 이동은 큰 것에서 작은 것으로 이동하여 다른 하위 나무의 상태와 비교하기 편리하다
그리고 상태 이동 방정식은 모든 자수가 자신에게 dfs를 진행할 때 독특하기 때문에 q-w는 이미 모든 자수의 여분의 물건을 계산했다
그리고 이 나무를 옮기는 것을 보면 그의 걸음걸이는 대략 이렇게 몇 가지가 가능하다.나무 뿌리에서 잎까지 2.나무 뿌리에서 한 그루 나무의 어느 노드로 다시 돌아가서 나무 뿌리로 다시 걸어 나오는 것이 문제다.dp[gen][q+2][0]는 현재 나무를 떠나 다른 나무로 가는 상황에 대한 dp[gen][q+2]와 dp[gen][q+1]은 서로 보충하는 상태 이동이다

#include
#include
#include
#include
using namespace std;
int dp[101][301][2],n,k,biaoji[101],zhi[101];
vector<int> li[101];
void maxi(int &a, int b)
{
    if (a < b)a = b;
}
void dfs(int gen)
{
    biaoji[gen] = 1;
    for (int a = 0; a < li[gen].size(); a++)
    {
        if (biaoji[li[gen][a]] == 0)
        {
            dfs(li[gen][a]);
            for (int q = k; q >= 0; q--)
            {
                for (int w = 0; w <= q; w++)
                {
                    maxi(dp[gen][q + 2][0], dp[li[gen][a]][w][0]+dp[gen][q-w][0]);
                    maxi(dp[gen][q + 2][1], dp[li[gen][a]][w][0] + dp[gen][q - w][1]);
                    maxi(dp[gen][q + 1][1], dp[li[gen][a]][w][1] + dp[gen][q - w][0]);
                }
            }
        }
    }
}
int main()
{
    while (cin >> n >> k)
    {
        memset(dp, 0, sizeof(dp));
        memset(zhi, 0, sizeof(zhi));
        memset(biaoji, 0, sizeof(biaoji));
        for (int a = 1; a <= n; a++)
        {
            li[a].clear();
            cin >> zhi[a];
        }
        int q, w;
        for (int a = 1; a <= n - 1; a++)
        {
            cin >> q >> w;
            li[q].push_back(w);
            li[w].push_back(q);
        }
        for (int a = 1; a <= n; a++)
            for (int b = 0; b <= k; b++)
                dp[a][b][0] = dp[a][b][1] = zhi[a];
        dfs(1);
        cout << max(dp[1][k][1], dp[1][k][0]) << endl;
    }
    return 0;
}