樹形DP問題

Placing Lampposts

題目傳送：UVA - 10859 - Placing Lampposts

巧妙的思想：

對于有兩個需要優化的量v1和v2的時候，要求首先滿足v1最小，在v1相同的情況下v2最小，則這裡可以把二者組合成一個量M*v1+v2，其中M是一個比”v2的最大理論值和v2的最小理論值之差”還要大的數。

AC代碼：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

vector<int> G[];
int vis[][], d[][];
int n, m;

int dp(int i, int j, int f) {
    if(vis[i][j]) return d[i][j];
    vis[i][j] = ;
    int& ans = d[i][j];

    ans = ;
    for(int k = ; k < G[i].size(); k ++) {
        if(G[i][k] != f) {
            ans += dp(G[i][k], , i);
        }
    }
    if(f >=  && !j) ans ++;

    if(j || f < ) {
        int sum = ;
        for(int k = ; k < G[i].size(); k ++) {
            if(G[i][k] != f) {
                sum += dp(G[i][k], , i);
            }
        }
        if(f >= ) sum ++;
        ans = min(ans, sum);
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T --) {
        scanf("%d %d", &n, &m);
        for(int i = ; i < n; i ++) G[i].clear();
        int a, b;
        for(int i = ;  i < m; i ++) {
            scanf("%d %d", &a, &b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        memset(d, , sizeof(d));
        memset(vis, , sizeof(vis));
        int ans = ;
        for(int i = ; i < n; i ++) {
            if(!vis[i][]) {
                ans += dp(i, , -);
            }
        }
        printf("%d %d %d\n", ans / , m - ans % , ans % );
    }
    return ;
}
           

刷油漆

題目傳送：hihoCoder - 1055 - 刷油漆

昨天第一次做樹形DP的題，感覺很神奇！思想甚是巧妙！

今天這個樹形DP是類似背包的一個題，因為遞推方程差不多

不過要注意一點，枚舉每一個子樹的那一層循環隻能放最外面

因為：

如果把枚舉每一個子樹放到最内層，枚舉”背包容量”放到最外面一層，則這樣會産生最優解沒有及時更新到最外面那一層的情況，導緻出錯。比如n=INF，m=9，根結點取1（因為必須取根節點），他有很多子樹，而取其中兩個子樹3個結點和5個節點為最優解。當取第二個子樹5個結點時，因為dp[1][4]（即第一個子樹的3個結點對應的應該已經更新的位置）還沒更新（因為是倒序枚舉m），此時得不到最優解。

AC代碼：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = ;
int dp[][];//dp[i][j]表示在以i為根的一棵樹中，選出包含根節點i的j個連通的結點，能夠獲得的最高的評分，然後我們的答案就是dp[1][m].

int n, m;
vector<int> G[maxn];

void dfs(int u, int fa) {
    int d = G[u].size();
    for(int i = ; i < d; i ++) {
        if(G[u][i] != fa) dfs(G[u][i], u);
    }
    for(int k = ; k < d; k ++) {//枚舉每一個子節點,這裡必須把枚舉每一個子節點放在外面，因為可能在周遊完這個子樹之後，再周遊另一個子樹可能會得到最優解，而每次隻枚舉每個子樹的一部分得不到最優解
        int v = G[u][k];
        if(v != fa)
        for(int j = m; j >= ; j --) {//倒序枚舉刷油漆的數量，類似背包
            for(int i = ; i < j; i ++) {
                dp[u][j] = max(dp[u][j], dp[u][j - i] + dp[v][i]);
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = ; i <= n; i ++) {
        scanf("%d", &dp[i][]);
    }
    int u, v;
    for(int i = ; i < n; i ++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(, -);
    printf("%d\n", dp[][m]);
    return ;
}