树形DP入门题目推荐以及解析

关于树形DP几道入门题目

今天恶补树形DP，感觉海星。

其实挺简单的。

介绍几道例题，我会的。

1.洛谷P1352 没有上司的舞会

我的一篇题解

我们可以考虑每一个节点都是有两种情况。

一个是被邀请；另一个是不会被邀请。

前者后果就是子节点不可以被选择；

后者结果就是子节点可以被选择。

于是关系明确，状态转移方程为：

dp[root][0] += std::max(dp[son[root][i]][0],dp[son[root][i]][1]);

dp[root][1] += dp[son[root][i]][0];

海星。

son[root][i]是当前节点的儿子。

初始化要记得是每一个点的快乐指数。

#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define Max 6050

#define re register

std::vector<int>son[Max];

int n,root,dp[Max][2],fa[Max];

void dfs(int root) {

	for(re int i = 0 ; i < son[root].size() ; ++ i)

		dfs(son[root][i]);

	for(re int i = 0 ; i < son[root].size() ; ++ i) {

		dp[root][0] += std::max(dp[son[root][i]][0],dp[son[root][i]][1]);

		dp[root][1] += dp[son[root][i]][0];

	}

}

void init() {

	scanf("%d",&n);int u,v;memset(fa,-1,sizeof fa);

	for(re int i = 1 ; i <= n ; ++ i) scanf("%d",&dp[i][1]);

	for(re int i = 1 ; i < n ; ++ i)

		scanf("%d%d",&u,&v),fa[u]=v,son[v].push_back(u);

	scanf("%d%d",&u,&v);

}

inline void print(int root) {printf("%d",std::max(dp[root][0],dp[root][1]));}

void work() {

	int root=1;

	while(fa[root] != -1) root = fa[root];

	dfs(root);

	print(root);

}

int main() {

	init();

	work();

	return 0;

}

2.poj1463 Strategic game

我们考虑每一个节点有两种情况。

一个是被选择；另一个是不被选择。

前者的结果是他的子节点可以被选择，也可以不被选择；

后者的结果是他的子节点必须备选择。

所以状态转移方程出来了：

dp[root][0] += std::max(dp[son[root][i]][0],dp[son[root][i]][1]);

dp[root][1] += dp[son[root][i]][0];

#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define Max 1550

#define re register

int n,dp[Max][2],fa[Max];

std::vector<int>son[Max];

void dfs(int root) {

	for(re int i = 0 ; i < son[root].size() ; ++ i)

		dfs(son[root][i]);

	for(re int i = 0 ; i < son[root].size() ; ++ i) {

		dp[root][0] += dp[son[root][i]][1];

		dp[root][1] += std::min(dp[son[root][i]][0],dp[son[root][i]][1]);

	}

}

void print(int root) {printf("%d\n",std::min(dp[root][0],dp[root][1]));}

void work() {

	int root=0;

	while(fa[root] != -1) root = fa[root];

	dfs(root);

	print(root);

}

void init() {

	int k,x,y;char ch;

	while(scanf("%d",&n) != EOF) {

		for(re int i = 0 ; i < n ; ++ i)

			fa[i] = -1,dp[i][0] = 0,dp[i][1] = 1;

		for(re int p = 1 ; p <= n ; ++ p) {

			scanf("%d",&k);std::cin >> ch;

			std::cin >> ch;scanf("%d",&y);

			std::cin >> ch;son[k].clear();

			for(re int i = 1 ; i  <= y ; ++ i)

				scanf("%d",&x),fa[x]=k,son[k].push_back(x);

		}

		work();

	}

}

int main() {

	init();

	return 0;

}

巴特西

树形DP入门题目推荐以及解析

关于树形DP几道入门题目

最新文章

热门文章