今天学习了树形dp~~依旧啥都没听懂~~

但是，我还是要水一篇博客：D

树形dp，顾名思义，是在树上dp。

以今天写的例题P1352 没有上司的舞会来讲。通过惊人的观察力，发现他是一道树形dp。所以我们首先要建树，于是：

CPP

for(int i = 1; i < n; ++i) {
	int l, k;
	cin >> l >> k;
	g[l].push_back(k);
	g[k].push_back(l);
}

很快就面临一个问题——没有根节点！ 我们知道，如果某人有上司，那么这个人一定是下属。所以我们只需要找出没有上司的人，就是他们的老总（即本题的根节点）。

于是我们可以用一个递归函数

dfs

来遍历每一个节点。

于是我们有了STD。

恩。

CPP

// 树形dp 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(6*(1e3)+10)
using namespace std;
int n;
int r[maxn], dp[maxn][2];
set<int> st;
vector<int> g[maxn];
void dfs(int now,int fa = -1) {
	dp[now][0] = 0;
	dp[now][1] = r[now];
	for(auto to : g[now]) {
		if(to == fa)
			continue;
		dfs(to, now);
		dp[now][0] += max(dp[to][0], 	dp[to][1]);
		dp[now][1] += dp[to][0];
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> r[i];
		st.insert(i);
	}
	memset(dp, 0xef, sizeof(dp));
	for(int i = 1; i < n; ++i) {
		int l, k;
		cin >> l >> k;
		g[l].push_back(k);
		g[k].push_back(l);
		st.erase(l);
	}
	int rt = *st.begin();
	dfs(rt);
	cout << max(dp[rt][0], dp[rt][1]);
	return 0;
}

恩。

生活愉快。

树形dp基础

文章操作

但是，我还是要水一篇博客：D

相关推荐

评论

树形dp基础