一类有依赖性的树形dp问题 【codsVS1378 选课】

tonyfang posted @ 2016年8月04日 09:17 in codevs with tags c++ OI , 836 阅读

大家好,我是(欧)洲人michaeljack(tonyfang);这节课我们来讲讲怎么搞基(学习)。

今天来讲的是一类有依赖性的树形dp问题

最著名的就是选课啦!Codevs1378

嗯然后我们讲讲普通的树形dp如何实现。

$f_{i,j}$表示以$i$为根的子树中,必须选$i$,而且选$j$个课的最大价值

然后我们发现,转移懵逼?!

$f_{i,j} = \sum_{i=1}^{son_{i}}f_{i, d_{i}}$,其中$\sum_{i=1}^{son_{i}} d_{i} = j$

啊这怎么枚举啊?黑人问号*n。

当然要用背包啦!设$g_{i,j}$表示当前这个节点前$i$棵子树,选了$j$个课的最大价值。

那么我们就可以这么写啦$g_{i,j} = max(g_{i,j}, g_{i, j-k} + f_{son[i], k})$。

然后转移就很简单啦$f_{i,j} = g_{i, j-1} + w_{i}$,复杂度可以证明是$O(nm)$

嗯这就做完啦!

 

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int n, m;
int fa[510], w[510], f[510][510], g[510][510], size[510];
int head[510], next[200010], to[200010], tot;
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dp(int x, int father) {
	size[x]=1; int as = 0;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		dp(to[i], x);
		size[x]+=size[to[i]];
		++as;
	}
	int j=0, To = min(m, size[x]);
	for (int i=0; i<=as; ++i)
		for (int k=1; k<=To; ++k) g[i][k]=0;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		++j;
		for (int k=1; k<=To; ++k)
			for (int ch=0; ch<=k; ++ch)
				g[j][k] = max(g[j][k], g[j-1][k-ch] + f[to[i]][ch]);
	}
	for (int i=1; i<=To+1; ++i)
		f[x][i] = max(f[x][i], g[j][i-1]+w[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) {
		scanf("%d%d", &fa[i], &w[i]);
		add(i, fa[i]);
		add(fa[i], i);
	}
	dp(0, -1);
	//for (int i=0; i<=n; ++i) 
	//	for (int j=1; j<=m; ++j)
	//		printf("i=%d, j=%d, f[i][j]=%d\n", i, j, f[i][j]);
	printf("%d\n", f[0][m+1]);
	return 0;
}

当然接下来才是本文重点,用dfs序来处理!

“首先我们处理出这个树的dfs序,然后我们乱搞就行了啊!”

“怎么乱搞啊?黑人问号*n”

嗯首先dfs序内子树一定是连续的一段区间,那么我们可以设$f[i, j]$表示以第i个点及以后的dfs序的大小为j的连通块的最大权值,那么我们就可以转移啦!

$f_{i,j} = max(f_{i+size[x], j}, f_{i+1, j-1}+w_{x})$

就没啦!

 

p.s 多叉树转二叉树的奇妙方法

把多叉树先转化成“左儿子,右兄弟”的表示方法。会发现形成这样一种结构图:多叉树:

转化成“左儿子,右兄弟”的二叉树:

# include <stdio.h>
# include <algorithm>
using namespace std;

int dfn[510], ndfn[510], n, m, w[510], idfn = 0;
int size[510];
int head[510], next[200010], to[200010], tot, f[510][510];
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int father) {
	size[x]=1; dfn[x] = ++idfn; ndfn[idfn]=x;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == father) continue;
		dfs(to[i], x);
		size[x]+=size[to[i]];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1, fa; i<=n; ++i) {
		scanf("%d%d", &fa, &w[i]);
		add(i, fa);
		add(fa, i);
	}
	dfs(0, -1);
	for (int i=n+1; i>=1; --i) {
		int x = ndfn[i];
		for (int j=1; j<=m+1; ++j) 
			f[i][j] = max(f[i+size[x]][j], f[i+1][j-1]+w[x]);		
	}
	printf("%d\n", f[1][m+1]);
	return 0;
}
TN +1 Model Paper 20 说:
2022年8月22日 01:56

This board oversees a large number of schools in the state of Tamil Nadu, and it makes every effort to give its pupils access to a top-notch education. This board also held 11th-class exams during the current academic year in the state of Tamil Nadu, and all students who registered for those exams are currently awaiting the TN +1 Important Question Paper 2023. TN +1 Model Paper 2023 The Directorate of Government Examinations, Tamil Nadu, released the TN 11th Question Paper 2023 for these examinations in May. Approximately 88.1% of the pupils that participated in the tests were successful.

jnanabhumiap.in 说:
2024年1月03日 20:55

JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter