HDU4616 Game (樹形DP/搜尋)

題目連結：傳送門 

題意：

給定一棵樹，樹上的每個點有一個權值，這個點可能有鎖也可能沒有鎖，一個節點不能被走兩次，如果你被鎖了C次那麼你就不能繼續往下走了，可以自己選擇起點，問所能得到的最大值是多少。

思路一：

直接根據題意，然後從葉節點開始暴力搜，由于題目的資料比較弱是以這種方法可以過。

代碼如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 50010;

int n,c;

struct Graph {
    vector<int >vc[maxn];
    bool vis[maxn];
    int lock[maxn];
    int val[maxn];
    void init() {
        memset(lock,0,sizeof(lock));
        for(int i=0; i<n; i++)
            vc[i].clear();
    }
    void add(int u,int v){
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    int dfs(int u,int pre,int num){
        vis[u]=1;
        int sum = val[u];
        num+=lock[u];
        if(num==c) return sum;
        int tmp = 0;
        for(int i=0;i<vc[u].size();i++){
            int v=vc[u][i];
            if(vis[v]||v==pre) continue;
            tmp=max(tmp,dfs(v,u,num));
        }
        return sum+tmp;
    }
}G;

int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&c);
        G.init();
        for(int i=0;i<n;i++)
            scanf("%d%d",&G.val[i],&G.lock[i]);
        for(int i=0;i<n-1;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G.add(u,v);
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            if(G.vc[i].size()==1){
                memset(G.vis,0,sizeof(G.vis));
                ans = max(ans,G.dfs(i,0,0));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
           

思路二：

設dp[u][j][k],表示從u孩子到u，被鎖了j次起點有鎖/沒鎖的最大值。然後dp[u][j+lock[u]][k]= max(dp[v][j][k]+val[u]) v為u的孩子。

代碼如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 50010;

int n,c;

int max2(int x, int y) {
    return x > y ? x : y;
}

struct Graph {
    vector<int >vc[maxn];
    int dp[maxn][4][2];
    bool vis[maxn];
    int lock[maxn];
    int val[maxn];
    int ans;
    void init() {
        ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<4; j++) {
                for(int l=0; l<2; l++)
                    dp[i][j][l] = -99999999;
            }
        }
        for(int i=0; i<n; i++)
            vc[i].clear();
    }
    void add(int u,int v) {
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    void dfs(int u,int pre) {
        dp[u][lock[u]][lock[u]]=val[u];
        for(int i=0; i<vc[u].size(); i++) {
            int v = vc[u][i];
            if(v==pre) continue;
            dfs(v,u);
            for(int j=0; j<=c; j++) {
                for(int k=0; k+j<=c; k++) {
                    ans = max2(ans,dp[u][j][1]+dp[v][k][1]);
                    if(j+k<c) ans = max2(ans,dp[u][j][0]+dp[v][k][0]);
                    ans = max2(ans,dp[u][j][0]+dp[v][k][1]);
                    ans = max2(ans,dp[u][j][1]+dp[v][k][0]);
                }
            }
            for(int j=0; j<c; j++) {
                dp[u][j+lock[u]][0]=max2(dp[u][j+lock[u]][0],dp[v][j][0]+val[u]);
                dp[u][j+lock[u]][1]=max2(dp[u][j+lock[u]][1],dp[v][j][1]+val[u]);
            }
            if(lock[u]==0) dp[u][c][1] = max2(dp[u][c][1],dp[v][c][1]+val[u]);
        }
    }
} G;

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&c);
        G.init();
        for(int i=0; i<n; i++)
            scanf("%d%d",&G.val[i],&G.lock[i]);
        for(int i=0; i<n-1; i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            G.add(u,v);
        }
        G.dfs(0,-1);
        printf("%d\n",G.ans);
    }
    return 0;
}