树形DP

前置知识

树形结构，线性DP

目标

树形DP模板题

What

给定一颗有 N 个结点的树（通常是无根树，也就是有 N - 1 条无向边），我们可以任选一个结点为根结点，从而定义出每个结点的深度和每棵子树的根。 在树上设计动态规划算法时，一般就以结点从深到浅（子树从小到大）的顺序作为 DP 的“阶段”，DP 的状态表示，第一维通常是结点编号（代表以该结点为根的子树）。 大多数的时候，我们采用递归的方式实现树形动态规划。 对于每个结点 x，先递归在它的每个子结点上进行 DP，在回溯的时候，从子结点向结点 x 进行状态转移。

How

例题，P1352 没有上司的舞会

题意，有 n 名职员，每个人都有一个快乐值。有 n-1 条边表示上下级关系，在参加舞会的时候，下级不希望和上级一起参加。在满足这个条件的情况下，一部分员工参加舞会，问是的所有参会员工的快乐值加起来最大能是多少

// f[x, 0]表示x作为子树根结点，x不参加舞会，子树中部分员工参加，可以获得的最大价值
// f[x, 1]表示x作为子树根结点，x参加舞会，子树中部分员工参加，可以获得的最大价值
// f[x, 0] = sum of max(f[son, 0], f[son, 1]) 
// f[x, 1] = H[x] + sum of f[son, 0]

#include <bits/stdc++.h>

using namespace std;

const int N = 60010;

int H[N], n;
vector<int> h[N];
bool vis[N];
int f[N][2], root = -1;

void dp(int x) {
    f[x][0] = 0, f[x][1] = H[x];

    for (auto son : h[x]) {
        dp(son);

        f[x][0] += max(f[son][0], f[son][1]);
        f[x][1] += f[son][0];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> H[i];
    for (int i = 1; i < n; i++) {
        int L, K;
        cin >> L >> K;
        h[K].push_back(L);
        vis[L] = true;
    }

    // 先找到根结点
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {root = i; break;}

    dp(root);
    cout << max(f[root][0], f[root][1]) << '\n';

    return 0;
}

题单

P2015 二叉苹果树 [P2014 CTSC1997] 选课 HDU 2196 Computer POJ 1463 Strategic game [POI2014]FAR-FarmCraft

总结

图、树的建立，还是正常建立

参考

《算法竞赛进阶指南》