[樹形dp] Jzoj P1046 尋寶之旅

Description

探險隊長凱因意外的弄到了一份黑暗森林的藏寶圖，于是，探險隊一行人便踏上了尋寶之旅，去尋找傳說中的寶藏。
藏寶點分布在黑暗森林的各處，每個點有一個值，表示藏寶的價值。它們之間由一些小路相連，小路不會形成環，即兩個寶藏點之間有且只有一條通路。探險隊從其中的一點出發，每次他們可以留一個人在此點開采寶藏，也可以不留，然后其余的人可以分成若干隊向這一點相鄰的點走去。需要注意的是，如果他們把隊伍分成兩隊或兩隊以上，就必須留一個人在當前點，提供聯絡和通訊，當然這個人也可以一邊開采此地的寶藏。并且，為了節約時間，隊伍在前往開采寶藏的過程中是不會走回頭路的。現在你作為隊長的助理，已經提供了這幅藏寶圖，請你算出探險隊所能開采的最大寶藏的價值。

Input

第一行有兩個正整數n(1<=n<=100)，表示藏寶點的個數，m(1<=m=100)表示探險隊的人數。
第二行是n個不超過100的正整數，分別表示1到n每個點的寶藏價值。
接下來的n-1行，每行兩個數，x和y(1<=x,y<=n,x<>y)，表示藏寶點x,y之間有一條路，數據保證不會有重復的路出現。
假設一開始探險隊在點1處。

Output

一個整數，表示探險隊所能獲得最大的寶藏價值。

Sample Input

5 3
1 3 7 2 8
1 2
2 3
1 4
4 5

?

?

題解

• 又是一道樹形dp，今天題做的要死了
• 題目說：

• 它們之間由一些小路相連，小路不會形成環，即兩個寶藏點之間有且只有一條通路

• 顯然就是棵樹
• 容易得到設f[i][j]以i為根的子樹，剩j的的最大價值
• 那就有兩種情況：
• ①當前點不挖，直接跳
• ②當前點留一個人挖，可以向下派j-1個人
• 則有 f[i][j]=max(f[i][j]，f[i][j-1-k]+f[son[i]][k]+v[i])

• 那么我們不知道在f[i][j-1-k]中是否有v[i]，如果有就算重了

• 可以多定一個數組g，也可以多加一維，其實是一樣的

• g[i][j]表示?]以i為根的子樹，剩j，不挖i 的的最大價值

代碼

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt,v[110],f[110][110],to[210],from[210],head[110],k[110],g[110][110];
void insert(int x,int y) { to[++cnt]=y; from[cnt]=head[x]; head[x]=cnt; }
void dp(int root,int fa)
{
    f[root][1]=v[root];
    for (int w=head[root];w;w=from[w])
        if (to[w]!=fa)
        {
            dp(to[w],root);
            for (int i=1;i<=m;i++) k[i]=max(f[root][i],f[to[w]][i]);
            for (int i=1;i<=m;i++)
                for (int j=1;j<i;j++)
                    k[i]=max(k[i],g[root][i-j-1]+f[to[w]][j]+v[root]);
            for (int i=1;i<=m;i++) f[root][i]=k[i];
            for (int i=1;i<=m;i++) k[i]=max(f[to[w]][i],g[root][i]);
            for (int i=1;i<=m;i++)
                for (int j=1;j<i;j++)
                    k[i]=max(k[i],g[root][i-j]+f[to[w]][j]);
            for (int i=1;i<=m;i++) g[root][i]=k[i];
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    for (int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert(x,y); insert(y,x);
    }
    dp(1,0);
    printf("%d",f[1][m]);
    return 0;
}

?