bzoj2830: [Shoi2012]随机树

题目链接

bzoj2830: [Shoi2012]随机树

题解

q1好做
设f[n]为扩展n次后的平均深度
那么(f[n] = frac{f[n - 1] * (n - 1) + f[n - 1] + 2}{n})
化简之后也就是(f[n] = f[n - 1] + frac{2}{n})
q2也好做
设f[i][j]表示扩展i次，树高为j的概率，对于左右儿子，子问题显然是一样的
枚举左右子树的i j 转移
(f[i][std::max(l,k) + 1] += f[j][k] * f[i - j][l] / (i - 1))
(n^4)可过

代码

#include<cstdio> 
#include<algorithm> 

inline int read() { 
	int x = 0,f = 1; 
	char c = getchar(); 
	while(c < '0' || c > '9')c = getchar(); 
	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
	return x * f; 
} 

const int maxn = 1007; 
int type,n; 
double f[maxn]; 
void solve1() { 
	f[0] = 0 ; 
	for(int i = 2;i <= n;++ i) 
		f[i] = f[i - 1] + 2.0 / i; 
	printf("%lf
",f[n]); 
} 
double F[maxn][maxn]; 
void solve2() { 
	F[1][0] = 1.0; 
	for(int i = 2;i <= n;++ i) 
		for(int j = 1;j < i;++ j) { 
			for(int k = 0;k <= j;++ k) 
				for(int l = 0;l <= (i - j);++ l) { 
					F[i][std::max(l,k) + 1] += F[j][k] * F[i - j][l] / (i - 1); 
				} 
		} 
	double ans = 0; 
	for(int i = 1;i <= n;++ i) ans += i * F[n][i]; 
	printf("%lf
",ans); 
} 
int main() { 
	type = read(),n = read(); 
	type == 1 ?  solve1() : solve2(); 
	return 0; 
}