树形DP

树形dp就是在树上进行的dp。由于树具有递归的性质，因此树形dp一半都是用递归的方式进行的。

问题的大意是，选了父节点，那么它的直接子节点就不能被选择，求总的权值的最大值。

题目：P1352 没有上司的舞会

这题是树形dp的板子题，每个节点都有被选择和不被选择两种情况。

用数组dp[n][0]记录第n个节点不被选择的情况，用数组dp[n][1]记录被选择的情况。

那么就有状态转移方程

dp[n][0] = Σ(max(dp[x][0],dp[x][1])，其中，x是n的所有子节点

dp[n][1] = a[n] + Σ(dp[x][0])

然后总的权值和的最大值就是 max(dp[root][0],dp[root][1])

下面给出代码实现：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 6006
typedef long long ll;

int r[MAXN];
int n;

//采用链式前向星的方式存储树
struct edge
{
    int u, v, next;

} e[4 * MAXN];

int head[MAXN];
int js_edge = 0;
void add_edge(int u, int v)
{
    js_edge++;
    e[js_edge].u = u;
    e[js_edge].v = v;
    e[js_edge].next = head[u];
    head[u] = js_edge;
}

ll dp[MAXN][2];
bool vis[MAXN] = {false};

void dfs(ll u)
{
    vis[u] = true;
    dp[u][1] = r[u];
    for (int i = head[u]; i != 0; i = e[i].next)
    {
        //被搜索过的就不再搜索
        if (vis[e[i].v])
            continue;

        dfs(e[i].v);
        dp[u][0] += max(dp[e[i].v][0], dp[e[i].v][1]);
        dp[u][1] += dp[e[i].v][0];
    }
}

bool is_root[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(is_root, 1, sizeof(bool) * MAXN);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> r[i];

    int l, k;
    for (int i = n + 2; i <= 2 * n; ++i)
    {
        cin >> l >> k;
        is_root[l] = false;
        add_edge(k, l);
    }

    for (int i = 1; i <= n; ++i)
    {
        //找到根节点
        if (is_root[i])
        {
            dfs(i);
            cout << max(dp[i][0], dp[i][1]) << endl;
            return 0;
        }
    }
}

转载请注明原文：https://www.longjin666.top/?p=994

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~