三道簡單樹型dp+01背包～～hdu1561，poj1947，zoj3626

以前學樹型dp就是隨便的看了幾道題，沒有特別注意樹型dp中的小分類的總結，直到上次浙大月賽一道很簡單的樹型dp都不會，才意識到自己太水了～～come on！

hdu1561：題目給出了很多棵有根樹，如果把每棵樹的根節點都與0相連，則就是一棵完整的有根樹了（N<=200），ACboy從根節點出發，他最多可以攻占m個城市，而每個城市的財富值不一定相同，問ACboy最多可以獲得多少財富。就是以每個跟節點做01背包就可以了，dp[i][j]表示以i為根節點已經攻占了j個城市獲得的最大財富。不過要注意一下最后要加上根節點的值，因為要求攻占了根節點才能往下攻占，當然節點0除外，具體見代碼和注釋：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define see(x) cout<<#x<<":"<<x<<endl;
using namespace std;
const int maxn = 205;
int w[maxn], dp[maxn][maxn];
vector<int> son[maxn];
int n, m;
void dfs(int x){
    int i, j, k;
    if(son[x].size()==0){
        dp[x][1] = w[x];
        return;
    }
    for(i=0;i<son[x].size();i++){
        dfs(son[x][i]);
    }
    for(i=0;i<son[x].size();i++){
        for(j=m;j>=0;j--){
            for(k=0;k<=j;k++){
                if(dp[son[x][i]][k]!=-1&&dp[x][j-k]!=-1){
                    dp[x][j] = max(dp[x][j],dp[son[x][i]][k]+dp[x][j-k]);
                }
            }
        }
    }
/*上面就是基本樹型DP加背包的基本解法了*/
    if(x!=0){  //x為0節點時，不需要這種要求
        for(j=m;j>=0;j--){//處理一下必須攻占根節點才能攻占剩下的子節點的條件，逆序正好可以處理完
            if(dp[x][j-1]!=-1){
                dp[x][j] = dp[x][j-1]+w[x];
            }
        }
    }
}
void Init(int n){
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=n;i++){
        dp[i][0] = 0;
    }
    for(int i=0;i<=n;i++){
        son[i].clear();
    }
}
int main(){
    int i, j, k, l;
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        Init(n);
        for(i=1;i<=n;i++){
            scanf("%d%d",&k,&w[i]);
            son[k].push_back(i);
        }
        w[0] = 0; dfs(0);
        printf("%d\n",dp[0][m]);
    }
}

poj1947：給出一棵有根樹，問孤立出大小為P的子樹要斷開多少邊。就是一個容量為p的背包，樹型dp。dp[i][j]表示以i為根孤立出j個節點的樹至少需要斷開多少條邊，于是dp[x][j] = min{dp[x1][j1]+dp[x2][j2]+dp[x3][j3]+……+dp[xn][jn]}，j1+j2+j3+……+jn = j，但是也不是完全這樣了，其實在對每個背包進行更新時，應該是dp[x][j] = min{dp[x][j],dp[son[x][i]][k]+dp[x][j-k]-2}，減2是因為要減去算了兩次的x到son[x][i]的那條邊，具體見代碼，寫的挺糾結的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 155;
vector<int> son[maxn];
bool vis[maxn];
int dp[maxn][maxn];
int n, p;
void dfs(int root, int x){
    int i, j, k;
    if(x==root) dp[x][1] = son[x].size();
    else dp[x][1] = son[x].size()+1;

    for(i=0;i<son[x].size();i++){
        dfs(root,son[x][i]);
    }
    for(i=0;i<son[x].size();i++){
        for(j=p;j>=0;j--){
            for(k=0;k<=j;k++){
                if(dp[x][k]<maxn&&dp[son[x][i]][j-k]<maxn){
                    dp[x][j] = min(dp[x][j],dp[x][k]+dp[son[x][i]][j-k]-2);
                }
            }
        }
    }
}
void Init(int n){
    int i, j;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            dp[i][j] = maxn;
        }
        son[i].clear();
        vis[i] = 0;
    }
}
int main(){
    int i, j, k, x1, x2, ans;
    while(~scanf("%d%d",&n,&p)){
        Init(n);
        for(i=0;i<n-1;i++){
            scanf("%d%d",&x1,&x2);
            son[x1].push_back(x2);
            vis[x2] = 1;
        }
        for(i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i,i);break;
            }
        }
        ans = maxn;
        for(i=1;i<=n;i++){
            ans = min(ans,dp[i][p]);
        }
        printf("%d\n",ans);
    }
}

zoj3626：這個就是上次浙大月賽的題了，題意跟hdu1561類似，給出一棵樹，n-1條邊有不同的邊全，n個城市有不同的財富，一個人最多只可以走m/2長度，為最多可以占領多少財富。dp[i][j]表示以i為根繼續走了j個長度可以獲得的最大財富，自己就是在刷完hdu1561之后簡單的改改順利的a了，兩道題可能可以改成一樣的寫法，不過想到怎么寫，就怎么寫了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define see(x) cout<<#x<<":"<<x<<endl;
using namespace std;
const int maxn = 110;
vector<int> son[maxn], w[maxn];
int val[maxn];
int dp[maxn][205];
int n, m;
void dfs(int x, int pre){
    int i, j, k;
    if(son[x].size()==1&&pre==son[x][0]){
        return;
    }
    for(i=0;i<son[x].size();i++){
        if(pre!=son[x][i]){
            dfs(son[x][i],x);
        }
    }
    for(i=0;i<son[x].size();i++){
        if(pre!=son[x][i]){
            for(j=m-w[x][i];j>=0;j--){
                for(k=0;k<=j;k++){
                    if(dp[son[x][i]][k]!=-1&&dp[x][j-k]!=-1){
                        dp[x][j+w[x][i]] = max(dp[x][j+w[x][i]],dp[son[x][i]][k]+dp[x][j-k]);
                    }
                }
            }
        }
    }
}
void Init(int n){
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=n;i++){
        son[i].clear();
        w[i].clear();
    }
}
int main(){
    int i, j, k, x1, x2, l, ans;
    while(~scanf("%d",&n)){
        Init(n);
        for(i=1;i<=n;i++){
            scanf("%d",&val[i]);
            dp[i][0] = val[i];
        }
        for(i=0;i<n-1;i++){
            scanf("%d%d%d",&x1,&x2,&l);
            son[x1].push_back(x2);w[x1].push_back(l);
            son[x2].push_back(x1);w[x2].push_back(l);
        }
        scanf("%d%d",&k,&m);
        m/=2;dfs(k,-1);
        ans = val[k];
        for(i=0;i<=m;i++){
            ans = max(ans,dp[k][i]);
        }
        printf("%d\n",ans);
    }
}

?按理說dp都沒啥模板，但是其實樹上dp+背包，如果不復雜的化，也有點按部就班的感覺了～下次想出狀態，尋軌道距應該就能做出來了。