夏晓光(loveJY)的博客

根据zhqwq的刷题记录来的

首先这是一道期望题,而且是经典树形DP题

第一问:

我一开始sb了,$f[i]$显然表示有i个叶子树的叶子深度期望均值,然后我枚举了左右子树的叶子个数并算出对应概率来转移,这显然是复杂的....

只需要考虑从i-1个叶子到第i个叶子,显然深度会增加2,平均后深度增加2/i,所以$f[i]=f[i-1]+2/i$

第二问:

不过我之前的想法还是有用处的,例如第二问?

根据第一问状态不难得到第二问状态是$dp[i][j]$表示有i个叶子且树深度恰好为j的期望

转移时我们要枚举左右儿子的叶子数和深度,$O(n^4)$,真自闭

所以我们有个经典trick----放松状态的限制!

$dp[i][j]$表示有i个叶子且树深度大于等于j的期望

这样转移的时候有一部分很好想出来

$dp[i][j]=\sum_{k=1}^{i-1}{dp[k][j-1]+dp[i-k][j-1]-dp[i-k][j-1]*dp[k][j-1]}$

看上去很不错,然而是错的 ,因为我们还没有乘上每种情况的概率呢

其实在第二问思考O(n^4)的时候就已经解决这个问题了,不过当时想的是右边只有1个叶子的情况

考虑组合计数

首先生成一个典开的序列方案数是第一次1个选择,第二次2个选择....$(k-1)!$种不同的方案

而生成左子树是(k-1)!,右子树就是(i-k-1)!

而我们又发现左子树右子树组合在一起形成一个01序列,0表示典开在左子树,1表示典开在右子树,这样的序列一共有$\binom{i-k-1+k-1}{k-1}=\frac{(i-2)!}{(i-k-1)!(k-1)!}$

发现了什么?我们这三个乘积是左子树k个右子树i-k个的总方案数,而这个东西是一定值

意味着每种情况的方案数相同

所以每种情况占比相同,都是$1/(i-1)$

code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int p,n;
double f[110],dp[110][110],ans;

int main() {
	scanf("%d%d",&p,&n);
	if(p==1) {
		f[1]=0;
		for(int i=2; i<=n; ++i)f[i]=f[i-1]+2.0/i;
		printf("%.6f",f[n]);
	} else {
		for(int i=1; i<=n; ++i)dp[i][0]=1;
		for(int i=2; i<=n; ++i) {
			for(int j=1; j<i; ++j) {
				for(int k=1; k<i; ++k) {
					dp[i][j]+=dp[k][j-1]+dp[i-k][j-1]-dp[k][j-1]*dp[i-k][j-1];
				}
				dp[i][j]/=(i-1);
			}
		}
		for(int i=1; i<n; ++i)ans+=dp[n][i];
		printf("%.6f",ans);
	}
	return 0;
}