C++高级算法：浅谈树形DP（例Anniversary Party、Computer）_计算机computer c++ 树形dp

目录

前言

例题一：Anniversary Party

题目描述

思路

最终代码

例题二：Computer（进阶）

题目描述

思路

最终代码

总结

前言

用了这么久的普通DP，终于了解到树形DP了。

依我所见，树形DP其实没有什么大不了的困难的。

简单来说，线性DP每个元素的状态转移方程依靠的是数组中其他元素，树形DP每个节点的状态转移方程依靠的是它的父、子节点。

不能一下理解的朋友看一下百科：

什么是树型动态规划 

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向： 

    1、叶－>根：在回溯的时候从叶子节点往上更新信息

    2、根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。

    不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分。

因为树本本身就有“子结构"的性质（子树），所以相对于线性DP来说，转移方程更直观、更易理解。

而且树形DP的题大多数是存在明显的树形结构的，所以很轻易就可以得出状态转移方程。

例题一：Anniversary Party

题目描述

Background

The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor relation forms a tree rooted at the president. Employees are numbered by integer numbers in a range from 1 to N, The personnel office has ranked each employee with a conviviality rating. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

Problem

Your task is to make up a guest list with the maximal conviviality rating of the guests.

Input

The first line of the input contains a number N. 1 ≤ N ≤ 6000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from –128 to 127. After that the supervisor relation tree goes. Each line of the tree specification has the form

<L> <K>

which means that the K-th employee is an immediate supervisor of L-th employee. Input is ended with the line

0 0

Output

The output should contain the maximal total rating of the guests.

Example

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

5

思路

大意就是给出每个节点的权值以及每对子节点和父节点，每对子节点和父节点不能共存，求所有存在的节点的权值和最大是多少。

每个节点的状态只有两个：存在/不存在，很容易就可以想出状态转移方程：

设表示节点 u 存在时，以它为根的子树的所有存在的节点的最大权值和，则表示 u 不存在。

方程为：

其中是 u 的儿子的集合。

为了更方便理解和运用，就用记忆化Dfs来完成树的结构的运算。

Dfs部分：

int dfs(int x,int y){    //y只有0或1
	if(v[x])return f[x][y];
	v[x]=1;
	int u=G[x].size();
	f[x][0]=0,f[x][1]=w[x];
	for(int o=0;o<u;o++){
		f[x][0]+=max(dfs(G[x][o],1),dfs(G[x][o],0));
		f[x][1]+=dfs(G[x][o],0);
	}
	return f[x][y];
}

怎么样？是不是很清晰很直白？

因为要求根节点的 f 值，而（经过多次测试发现）根节点的 f 值必定大于其他节点的 f 值，所以把所有节点 u 的和的最大值中的最大值输出就是答案。由于记忆化搜索不会有多余的运算，所以这样做不会超时。 

最终代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,i,j,l,k,w[6005],f[6005][2],ans;
vector<int>G[6005];
bool v[6005];
inline int read(){
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
int dfs(int x,int y){
	if(v[x])return f[x][y];
	v[x]=1;
	int u=G[x].size();
	f[x][0]=0,f[x][1]=w[x];
	for(int o=0;o<u;o++){
		f[x][0]+=max(dfs(G[x][o],1),dfs(G[x][o],0));
		f[x][1]+=dfs(G[x][o],0);
	}
	return f[x][y];
}
int main()
{
	n=read();
	for(i=1;i<=n;i++)w[i]=read();
	l=read(),k=read();
	while(l||k){
		G[k].push_back(l);
		l=read(),k=read();
	}
	for(i=1;i<=n;i++)ans=max(ans,max(dfs(i,1),dfs(i,0)));
	printf("%d",ans);
	putchar('\n');
	return 0;
}

例题二：Computer（进阶）

题目描述

A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information. 

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input

Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.

Output

For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input

5
1 1
2 1
3 1
1 1

Sample Output

3
2
3
4
4

思路

题目大意是给定一棵树，求每个节点到距离它最远的节点的距离。

节点 u 到距离它最远的节点的路径只有两种：往 u 的子节点延伸、往 u 的父节点延伸。

设表示往 u 的子节点延伸的最长路径，表示往 u 的父节点延伸的最长路径。

先看第一种：u 往它的子节点 v 延伸，那它的子节点 v 也只能往子节点方向延伸，因为如果 v 要往它的父节点延伸，只会又撞到 u ，然后就形成环了（显然是不符合要求的）。所以就是要加上。

状态转移方程为：$f1(u)=max(f1(v)+w(u,v))$

这部分Dfs为：

int dfs1(int x){
	if(v1[x])return f1[x];
	v1[x]=1;
	int u=G[x].size();
	f1[x]=0;
	for(int o=0;o<u;o++)
		f1[x]=max(f1[x],dfs1(G[x][o].e)+G[x][o].w);
	return f1[x];
}

第二种：u 往它的父节点 a 延伸，那它的父节点 a 往哪边延伸？显然又有两种情况： a 往子节点延伸、 a 往父节点延伸。

a 往父节点延伸很简单，只需调用一次。

a 往子节点延伸的话，就不能直接调用了，因为可能是往 u 延伸的，所以要枚举一遍 a 的所有子节点 b 除了 u （几乎重复Dfs1的过程），从中选出最大的。

最后加上 a 到 u 的距离。

然后就真的没有其他特殊情况了。

状态转移方程为：$f2(u)=max(max(f1(b)+w(a,b)),f2(a))+w(a,u)$。

这部分Dfs为：

int dfs2(int x){
	if(v2[x])return f2[x];
	v2[x]=1;
	if(x==1)return 0;
	int u=fa[x].e,r=G[u].size();
	f2[x]=0;
	for(int o=0;o<r;o++)
		if(G[u][o].e!=x)
			f2[x]=max(f2[x],dfs1(G[u][o].e)+G[u][o].w);
	f2[x]=max(f2[x],dfs2(u));
	f2[x]+=fa[x].w;
	return f2[x];
}

发现没有？函数的间接递归！

每个节点到距离它最远的节点的距离就是。

最终代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,i,j,l,k,f1[10005],f2[10005];
struct itn{
	int e,w;
	itn(){}itn(int E,int W){e=E,w=W;}
}fa[10005];
vector<itn>G[10005];
bool v1[10005],v2[10005];
inline int read(){
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
int dfs1(int x){
	if(v1[x])return f1[x];
	v1[x]=1;
	int u=G[x].size();
	f1[x]=0;
	for(int o=0;o<u;o++)
		f1[x]=max(f1[x],dfs1(G[x][o].e)+G[x][o].w);
	return f1[x];
}
int dfs2(int x){
	if(v2[x])return f2[x];
	v2[x]=1;
	if(x==1)return 0;
	int u=fa[x].e,r=G[u].size();
	f2[x]=0;
	for(int o=0;o<r;o++)
		if(G[u][o].e!=x)
			f2[x]=max(f2[x],dfs1(G[u][o].e)+G[u][o].w);
	f2[x]=max(f2[x],dfs2(u));
	f2[x]+=fa[x].w;
	return f2[x];
}
int main()
{
	while(scanf("%d",&n)==1){
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		memset(v1,0,sizeof(v1));
		memset(v2,0,sizeof(v2));
		memset(fa,0,sizeof(fa));
		for(i=1;i<=n;i++)G[i].clear();
		for(i=2;i<=n;i++){
			l=read(),j=read();
			G[l].push_back(itn(i,j));
			fa[i]=itn(l,j);
		}
		for(i=1;i<=n;i++){
			printf("%d",max(dfs1(i),dfs2(i)));
			putchar('\n');
		}
	}
	return 0;
}

总结

同前言里的百科。