打卡第二天 树形DP初步

1.P1352 没有上司的舞会

题目概述：

有n个人，除老板外每个人都有自己的上司k和快乐值l，但每个人都不能和自己的上司同时出现在舞会上，舞会的快乐值为所有到达舞会的人的快乐值总和，求其最大值。

题目分析：

每个人都有自己的上司且只有一个，这就组成了一棵树，因为只有一个老板，所以也就不存在森林，那么第一步需找到老板是谁，用for一层搞定。

对于f数组，他要有去或不去两种状态和当前人数编号，二维，用f[i][0/1]表示第i个人去/不去时以他子树的最大快乐值，可得

f[i][0](不去) = max(f[son][0],f[son][1]);

f[i][1](去) = f[son][0] + l[i]

代码如下

#include <iostream>
#include <bits/stdc++.h>
#define maxn 6005
#define minr -1000000

using namespace std;

int n;
int r[maxn];
vector<int> son[maxn];
bool appear[maxn] = {false};
int dp[maxn][2];
bool reference[maxn] = {false};

void Dp (int x) {
	reference[x] = true;
	
    int f = 0;
    int s = 0;

	for (int i = 0; i < son[x].size(); i++) {
		if (!reference[son[x][i]]) {
			Dp(son[x][i]);
		}
		
        f += max(dp[son[x][i]][0],dp[son[x][i]][1]);
        s += dp[son[x][i]][0];
	}

    dp[x][0] = f;
    dp[x][1] = s + r[x];

    // cout << x << " " << dp[x][0] << " " << dp[x][1] << endl;
	
	return;
}

int main () {
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> r[i];
	}
	
	for (int i = 1; i <= n - 1; i++) {
		int a,b;
		cin >> a >> b;
		son[b].push_back(a);
		appear[a] = true;
	}
	
	int root;
	
	for (int i = 1; i <= n; i++) {
		if (!appear[i]) {
			root = i;
			break;
		}
	}
	
	for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = minr;
    }
	
	Dp(root);
	
	cout << max(dp[root][1],dp[root][0]);
	
	return 0;
}

2.P2014 [CTSC1997] 选课

题目概括：

现在这群人变了，除非他们的上司到舞会他们才肯去，并且许多人都成了老板，且舞会大小有限，只能容纳n个人，求总快乐值最大值。

题目思路：

方便起见，我们定义编号0为终极老板

用vector<int> son[maxn]记录每个人的所有下属，用背包的形式完成

若f[x][t]表示以x为根的子树中取t项所得到的最大值

则可视作01背包

for (int t = m; t >= 0; t--) {
            for (int j = 0; j <= t; j++) {
                f[x][t] = max(f[x][t],f[x][t - j] + f[y][j]);
            }
        }

 最后别忘了加上x本身的快乐值

void dp (int x) {
    f[x][0] = 0;
    
    for (int i = 0; i < son[x].size(); i++) {
        int y = son[x][i];
        dp(y);

        for (int t = m; t >= 0; t--) {
            for (int j = 0; j <= t; j++) {
                f[x][t] = max(f[x][t],f[x][t - j] + f[y][j]);
            }
        }
    }

    if (x != 0) {
        for (int t = m; t > 0; t--) {
            f[x][t] = f[x][t - 1] + s[x];
        }
    }
}

3.P3478 [POI2008] STA-Station

二次扫描与换根法

定义f[n]表示以n为根的最大深度和，则对f[i]可用O(n)记忆化暴力求解

void dfsD (int x,int t) {
    v[x] = true;
    long long res = t;
    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if (!v[y]) {
            dfsD(y,t + 1);
        }
        res += d[y];
    }

    d[x] = res;
}

对于f[i] 与 f[son[i]]，son[i]的子树深度均减一，其他点深度均加一

所以f[son[i]] = f[i] - large[son[i]] + (n - large[son[i]])

求f[son[i]]的时间复杂度为O(1)

总时间复杂度为O(n)

对于large需要在初始枚举时预处理

#include <bits/stdc++.h>

using namespace std;

vector<int> G[1000005];
int n;
long long d[1000005];
long long f[1000005];
long long large[1000005] = {0};
bool v[1000005];

void dfsD (int x,int t) {
    v[x] = true;
    long long res = t;
    large[x] = 1;

    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if (!v[y]) {
            dfsD(y,t + 1);
            large[x] += large[y];
        }
        res += d[y];
    }

    d[x] = res;
}

void dfsF (int x) {
    v[x] = 1;

    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if (v[y]) continue;
        f[y] = f[x] - large[y] + n - large[y];
        dfsF(y);
    }
}

int main () {

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u,v;
        cin >> u >> v;

        G[u].push_back(v);
        G[v].push_back(u);
    }

    memset(v,0,sizeof(v));
    dfsD(1,0);

    f[1] = d[1];
    memset(v,0,sizeof(v));

    dfsF(1);
    
    long long res = 0;
    int c;
    for (int i = 1; i <= n; i++) {
        if (res < f[i]) {
            res = f[i];
            c = i;
        }
    }
    cout << c << endl;

    return 0;
}