『没有上司的舞会树形DP』

<更新提示>

<第一次更新>

<正文>

树形DP入门

有些时候，我们需要在树形结构上进行动态规划来求解最优解。

例如，给定一颗\(N\)个节点的树(通常是无根树，即有\(N-1\)条无向边)，我们可以选择任意节点作为根节点从而定义出每一颗子树的深度，形成一个子问题重叠的结构，是符合动态规划前提的。在设计动态规划算法时，一般由节点由深到浅的顺序来作为\(DP\)的阶段。\(DP\)的状态表示中，数组的第一维通常表示子树根节点的编号。大多数时候，我们用递归的形式实现树形动态规划。先在它的每个子节点上递归求出最优解，再在返回时求解当前节点的最优解。

下面我们通过一道入门例题来讲解。

没有上司的舞会(TYVJ1052 CODEVS1380)

Description

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

Input Format

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0,0。

Output Format

输出最大的快乐指数。

Sample Input

Sample Output

Hint

Limitation

各个测试点1s

解析

通过分析可以发现，职员和上司之间的关系可以看作为是一个树形结构，又是最优解问题，可以尝试树形\(DP\)。

根据之前我们对树形\(DP\)的初步了解，我们先设置\(DP\)的状态，并将根节点编号作为第一维。分析题意，我们发现一个人是否参加舞会只和他的直接上司有关，所以我们可以把第二维设为\(0/1\)，这样，\(f[i][0/1]\)代表以i号节点为根节点的子树结构中的最大快乐指数值之和，\(0\)代表\(i\)号职员不参加晚会，\(1\)代表\(i\)号职员参加晚会，这样的状态，是满足最优子结构的。

利用阶段和之前的状态建立关系。如果i参加晚会，则他的下属不能参加晚会，如果他不参加晚会，则他的下属可以参加晚会，当然，也可以不参加。 那么，我们就可以写出状态转移方程:

\[1.f[i][1]=h[i]+\sum_{s\in Son(i)}f[s][0]
\\2.f[i][0]=\sum_{s\in Son(i)}max(f[s][1],f[s][0])
\]

其中，\(Son(i)\)代表节点i的子节点集合。

本题当中，我们还需要找到有根树的根，即没有上司的职员，然后从他开始进行\(DP\)求解。最终，\(DP\)的目标状态是\(max(f[root][1],f[root][0])\)。时间复杂度为\(O(n)\)。

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

const int N=6000+80;

int n,h[N]={},f[N][2]={},vis[N]={};

vector < int > son[N];

inline void read(int &k)

{

	int x=0,w=0;char ch;

	while(!isdigit(ch))w|=ch=='-',ch=getchar();

	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

	k=(w?-x:x);return;

}

inline void input(void)

{

	read(n);

	for(int i=1;i<=n;i++)read(*(h+i));

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

	{

		int f,s;

		read(s),read(f);

		vis[s]=true;

		son[f].push_back(s);

	}

}

inline void dp(int root)

{

	f[root][0]=0;f[root][1]=h[root];

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

	{

		int S=son[root][i];

		dp(S);

		f[root][0]+=max(f[S][1],f[S][0]);

		f[root][1]+=f[S][0];

	}

}

inline void solve(void)

{

	memset(f,0,sizeof f);

	int root;

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

	{

		if(!vis[i]){root=i;break;}

	}

	dp(root);

	printf("%d\n",max(f[root][0],f[root][1]));

}

int main(void)

{

	freopen("test.in","r",stdin);

	freopen("test.out","w",stdout);

	input();

	solve();

	return 0;

}

总结

通过一道例题，我们对树形DP建立的初步的认识。但是，在更复杂的题目中，我们需要学习更多的技巧，例如，出来自顶向下的递归以外，我们还可以运用图上DP的方法，用自底向上的拓扑序来执行树形DP，但是实现更为复杂，通常来说，这样的DP已经足够。

在更多的题目中，树是以一张N个点，N-1条边的无向图的形式给出的，这样的话我们还需要找出树的根，一般是用深搜的方法。

<后记>

巴特西

『没有上司的舞会树形DP』

树形DP入门

没有上司的舞会(TYVJ1052 CODEVS1380)

Description

Input Format

Output Format

Sample Input

Sample Output

Hint

Limitation

解析

总结

最新文章

热门文章

巴特西

『没有上司的舞会 树形DP』

树形DP入门

没有上司的舞会(TYVJ1052 CODEVS1380)

Description

Input Format

Output Format

Sample Input

Sample Output

Hint

Limitation

解析

总结

最新文章

热门文章

『没有上司的舞会树形DP』