看看树形 DP 是怎么个东西

关于这段时间尝试巴结树形 DP 这件事.jpg

感悟

暂无.jpg

题目

可能更多的是代码记录罢了.jpg

P1272 重建道路

依旧是看了半天题解才看明白，但是题解几种做法不太一样，但是转移方程是差不多的。

还是太弱了.jpg

代码：

#include <iostream>
#include <vector>

int n, p;
std::vector<std::vector<int>> e; // 存图
std::vector<std::vector<int>> f; // f[i][j]表示以 i 为根保留 j 个 节点所需要删掉的边的最小数量
std::vector<int> deg; // 出度计数

int dfs(int u) {
    int sum = 1, siz; // 自己也算一个节点
    for (int v : e[u]) {
        siz = dfs(v);
        sum += siz;
        for (int j = sum; j >= 1; j--) {
            for (int k = 1; k < j; k++) {
                f[u][j] = std::min(f[u][j], f[u][j - k] + f[v][k] - 1); // 减掉的是 u 与 v 相连的那条边
            }
        }
    }
    return sum;
}

int main() {
    std::cin >> n >> p;
    e.resize(n + 1);
    f.resize(n + 1, std::vector<int>(n + 1, 0x3f3f3f3f));
    deg.resize(n + 1);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        deg[u]++; // 子节点数增加，出度
        e[u].emplace_back(v);
    }
    for (int i = 1; i <= n; i++) {
        f[i][0] = 0; // 保留 0 自然是 0
        f[i][1] = deg[i]; // 保留 1 就是子节点数
    }
    dfs(1);

    int ans = f[1][p];
    for (int i = 1; i <= n; i++) {
        if (ans > f[i][p]) ans = f[i][p] + 1; // 除 1 以外，保留一棵子树还需要断掉 u 与 parent[u] 相连的那条边
    }

    std::cout << ans << '\n';
    return 0;
}

P1273 有线电视网

感觉比上一题好理解诶，也可能这题我前一天写过的原因（。

代码：

#include <iostream>
#include <vector>

const int INF = 0x3f3f3f3f;

int n, m;
std::vector<std::vector<std::pair<int, int>>> e;
std::vector<std::vector<int>> f; // f[i][j] 表示以 i 为根服务 j 个用户所获得的钱钱
std::vector<int> p; // 用户愿意交的钱钱

bool is_user(int u) { return u > n - m; } // 根据题意 u > n - m 就是用户

int dfs(int u) {
    if (is_user(u)) { 
        return 1; // 诶诶，这个是用户
    }
    int sum = 0, siz; // sum 为以 u 为根下的用户数量, siz 为以 v 为根下的用户数量
    for (auto [v, w] : e[u]) {
        siz = dfs(v);
        sum += siz;
        for (int j = sum; j >= 1; j--) {
            for (int k = 1; k <= j; k++) { // 一定是 k <= j，因为可以全部都在 v 为根的子树里面取
                f[u][j] = std::max(f[u][j], f[u][j - k] + f[v][k] - w); // 减去传输边需要的钱
            }
        }
    }
    return sum;
}

int main() {
    std::cin >> n >> m;
    e.resize(n + 1);
    p.resize(n + 1);
    f.resize(n + 1, std::vector<int>(n + 1, -INF));

    for (int u = 1; u <= n - m; u++) {  // 题意建图
        int siz, v, w;
        std::cin >> siz;
        while (siz--) {
            std::cin >> v >> w;
            e[u].push_back({ v, w });
        }
    }

    for (int i = n - m + 1; i <= n; i++) { // 读入用户愿意花的钱钱
        std::cin >> p[i]; 
    }

    for (int i = 1; i <= n; i++) { 
        f[i][0] = 0; // 不服务当然是 0
        if (is_user(i)) f[i][1] = p[i]; // 是用户的话 f[user][1] = p[user]
    }

    dfs(1);

    for (int i = n; i >= 1; i--) { // 尽可能多的用户，倒序枚举
        if (f[1][i] >= 0) { // 大于等于，不亏本
            std::cout << i << '\n';
            break;
        }
    }
    return 0;
}

P2014 选课

妈耶我为什么写过了还是写不出来我不理解，卡在以 0 为根节点和 m + 1 个选项那了emmmm

但是确实是很简单的，但是我是fw.jpg

代码：

#include <iostream>
#include <vector>

int n, m;
std::vector<std::vector<int>> e;
std::vector<std::vector<int>> f;

void dfs(int u) {
    for (int v : e[u]) {
        dfs(v);
        for (int j = m + 1; j >= 0; j--) {
            for (int k = 0; k < j; k++) { // parent[v] 必选
                f[u][j] = std::max(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
}

int main() {
    std::cin >> n >> m;
    e.resize(n + 1);
    f.resize(n + 1, std::vector<int>(m + 2));

    for (int v = 1; v <= n; v++) {
        int u, w;
        std::cin >> u >> w;
        e[u].push_back(v);
        f[v][1] = w;
    }
    dfs(0); // 以 0 作为根节点，所以要选 m + 1 个
    std::cout << f[0][m + 1] << '\n';
    return 0;
}

P2585 三色二叉树

根据题意写转移方程就好，相邻节点不能同色。

代码：

#include <iostream>
#include <string>
#include <array>
#include <algorithm>

enum Color { R, G, B }; // 对应三种颜色，红，绿，蓝

struct Node {
    Node *childl, *childr;
    std::array<int, 3> fn, fm; // fn[u][R/G/B] 将 u 染对应颜色绿色个数的最小值, fm 最大值
    Node () : childl(nullptr), childr(nullptr), fn({ 0, 0, 0 }), fm({ 0, 0, 0 }) {}; // 初始化
};

Node* build(std::string &s, Node *nul) {
    Node *curr = new Node();
    char t = s.back();
    s.pop_back();

    if (t == '1') { // 为了方便，只有左节点的用空节点补成完全二叉树
        curr->childl = build(s, nul);
        curr->childr = nul;
    } else if (t == '2') {
        curr->childl = build(s, nul);
        curr->childr = build(s, nul);
    }
    return curr;
}

void dfs(Node *curr, Node *nul) {
    if (curr->childl && curr->childl != nul) dfs(curr->childl, nul); // 不为 nullptr 并且不为空节点，进行遍历
    if (curr->childr && curr->childr != nul) dfs(curr->childr, nul); // 同上

    if (!curr->childl && !curr->childr) {
        curr->fn[G] = 1;
        curr->fm[G] = 1;
        return;
    }

    // 很好理解，根据题目意思三种颜色的转移
    curr->fn[G] = std::min(curr->childl->fn[R] + curr->childr->fn[B], curr->childl->fn[B] + curr->childr->fn[R]) + 1;
    curr->fn[R] = std::min(curr->childl->fn[G] + curr->childr->fn[B], curr->childl->fn[B] + curr->childr->fn[G]);
    curr->fn[B] = std::min(curr->childl->fn[G] + curr->childr->fn[R], curr->childl->fn[R] + curr->childr->fn[G]);

    curr->fm[G] = std::max(curr->childl->fm[R] + curr->childr->fm[B], curr->childl->fm[B] + curr->childr->fm[R]) + 1;
    curr->fm[R] = std::max(curr->childl->fm[G] + curr->childr->fm[B], curr->childl->fm[B] + curr->childr->fm[G]);
    curr->fm[B] = std::max(curr->childl->fm[G] + curr->childr->fm[R], curr->childl->fm[R] + curr->childr->fm[G]);
}

int main() {
    std::string s;
    std::cin >> s;
    std::reverse(s.begin(), s.end()); // 反转，后续用 pop_back

    Node *nul = new Node(); // 空节点
    Node *root = build(s, nul);
    dfs(root, nul);
    std::cout << std::max({ root->fm[R], root->fm[G], root->fm[B] }) << ' ' << std::min({ root->fn[R], root->fn[G], root->fn[B] }) << '\n';
    return 0;
}