提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

树形DP

2023-04-18 15:38:04 时间

树形 DP

一、简单树形DP

树形 (DP)，即在树上进行 (DP),一般以递归进行，以板题为例：没有上司的舞会。
(Rightarrow) 分析：对于一个结点 (x)，其一个儿子结点为 (y)，分两种情况：
（1）如果 (x) 不去，那么他的儿子结点可去可不去，即：

[f_{x,0}=sum max(f_{y,0},f_{y,1}) ]

（2）如果 (x) 去，那么他的儿子结点只能不去，即：

[f_{x,1}=sum f_{y,0} ]

(Rightarrow) 代码实现：
（1）输入的时候输入的值相当于最开始的 (f_{i,1})。
（2）利用 (dfs) 递归记录每个结点的值即可。
（3）(dfs) 要从根节点开始，此时我们只要根据输入来判断，对于每一个 (l_i) 肯定不是根节点，所以最后看哪一个点没有在 (l_i) 中出现过即是根节点。

点击查看代码 
#include <iostream>
#include <cstdio>
#define N 6003

using namespace std;

int n,f[N][2],jilu[N],vis[N];

struct edge{
	int next,to;
}edge[N];
int head[N],cnt;
void add(int from,int to){
	edge[++cnt].next = head[from];
	edge[cnt].to = to;
	head[from] = cnt;
}

void Input(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++) scanf("%d",&f[i][1]);
	for(int i = 1,l,k;i < n;i ++){
		scanf("%d%d",&l,&k);
		add(k,l);jilu[l] = 1;
	}
}

void dfs(int x){
	vis[x] = 1;
	for(int i = head[x];i;i = edge[i].next){
		int y = edge[i].to;
		if(vis[y]) continue;
		dfs(y);
		f[x][1] += f[y][0];
		f[x][0] += max(f[y][1],f[y][0]);
	}
}

void work(){
	for(int i = 1;i <= n;i ++){
		if(!jilu[i]){
			dfs(i);
			printf("%d
",max(f[i][0],f[i][1]));
			return ;
		}
	}
}

int main(){
	Input();
	work();
	return 0;
}

二、树上背包

其实也就是树形 (DP) 和背包的结合啦。
还是以题为例：

选课

(Rightarrow) 分析：每一门功课都最多有一门先修课，所以可以看成一个树形结构。
考虑如何实现状态转移，令 (f_{x,i,j}) 表示对于结点 (x)，已经遍历了其前 (i) 个叶子结点，共学习 (j) 门功课可以获得的最大学分。
从三维的角度分析，我们令每个结点的叶子结点所有的编号依次递增，那么：

[f_{x,i,j} = max(f_{x,i - 1,j},f_{x,i - 1,k} + f_{y,siz_y,j - k}) ]

其中 (y) 表示 (x) 的第 (i) 个叶子结点，(siz[y]) 表示 (y) 的子树的大小。

如果卡空间怎么办？——考虑可否去掉一维。
刚刚的问题其实就想到于对于一个结点的贡献进行 (01) 背包来计算，所以类似 (01) 背包一样，可以去掉第二维，即：

[f_{x,j} = max(f_{x,j},f_{x,k} + f_{y,j - k}) ]

(Rightarrow) 代码实现：
（1）输入的时候相当于输入最开始时候的 (f_{i,1})。
（2）可以根据题意，把 (0) 作为根节点，但是处理的时候要注意：一共要取 (m + 1) 门功课，因为 (0) 必须的选。

点击查看代码 
#include <iostream>
#include <cstdio>
#define N 305

using namespace std;

int n,m,f[N][N],siz[N],vis[N];

struct edge{
	int next,to;
}edge[N];
int head[N],cnt;
void add(int from,int to){
	edge[++cnt].next = head[from];
	edge[cnt].to = to;
	head[from] = cnt;
}

void Input(){
	scanf("%d%d",&n,&m);
	for(int i = 1,k;i <= n;i ++) {
		scanf("%d%d",&k,&f[i][1]);
		add(k,i);
	}
}

void dfs(int x){
	vis[x] = 1;
	for(int i = head[x];i;i = edge[i].next){
		int y = edge[i].to;
		if(vis[y]) continue;
		dfs(y);
		for(int j = m + 1;j >= 1;j --){
			for(int k = 1;k <= j;k ++){
				f[x][j] = max(f[x][j],f[x][k] + f[y][j - k]);
			}
		}
	}
}

void work(){
	dfs(0);
	printf("%d",f[0][m + 1]);
}

int main(){
	Input();
	work();
	return 0;
}

二叉苹果树

(Rightarrow) 分析：与上题基本类似，只不过有一个地方不太一样：上题相当于选结点，但是本题相当于选路径，所以在状态转移上有小的差别。
仍然，令 (f_{x,i,j}) 表示对于结点 (x)，已经遍历了其前 (i) 个叶子结点，共选 (j) 个树枝可以获得的最多的苹果。
从三维的角度分析，我们令每个结点的叶子结点所有的编号依次递增，那么：

[f_{x,i,j} = max(f_{x,i - 1,j},f_{x,i - 1,k} + f_{y,siz_y,j - k - 1} + w_{x,y}) ]

还是可以像 (01) 背包一样，去掉第二维：

[f_{x,j} = max(f_{x,j},f_{x,k} + f_{y,j - k - 1} + w_{x,y}) ]

(Rightarrow) 代码实现：注意循环顺序已经循环的端点即可。

点击查看代码 
#include <iostream>
#include <cstdio>
#define N 105

using namespace std;

int n,Q,vis[N],f[N][N];

struct edge{
	int next,to,dis;
}edge[N << 1];
int head[N],cnt;
void add(int from,int to,int dis){
	edge[++cnt].next = head[from];
	edge[cnt].to = to;
	edge[cnt].dis = dis;
	head[from] = cnt;
}

void Input(){
	scanf("%d%d",&n,&Q);
	for(int i = 1,u,v,w;i < n;i ++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
}

void dfs(int x){
	vis[x] = 1;
	for(int i = head[x];i;i = edge[i].next){
		int y = edge[i].to;
		if(vis[y]) continue;
		dfs(y);
		for(int j = Q;j >= 1;j --){
			for(int k = 0;k < j;k ++){
				f[x][j] = max(f[x][j],f[x][k] + f[y][j - k - 1] + edge[i].dis);
			}
		}
	}
}

void work(){
	dfs(1);
	printf("%d",f[1][Q]);
}

int main(){
	Input();
	work();
	return 0;
}

相关文章