洛谷P3830 随机树（SHOI2012）概率期望DP

题意：中文题，按照题目要求的二叉树生成方式，问（1）叶平均深度（2）树平均深度

解法：这道题看完题之后完全没头绪，无奈看题解果然不是我能想到的qwq。题解参考https://blog.csdn.net/Maxwei_wzj/article/details/82262755这位大佬的，这里讲下我的理解：

首先是第一问：第一问会简单一些，设f[i]代表叶节点为i的树的叶平均深度，那么因为是平均那么 i*f[i] 就是叶子总深度啦。在叶子深度x下拓展得到的新贡献是 2(x+1)-x=x+2 。那么就有 i*f[i]=(i-1)*f[i-1]+x+2 。这里的x是什么呢？x是叶子深度当然要是期望情况下的深度，那不就恰好是f[i]吗！！

那么得到 i*f[i]=(i-1)*f[i-1]+f[i-1]+2 化简得到 f[i]=f[i-1]+2/n 。第一问解决。

第二问思维难度会更大一些：令g[i][j]代表叶子数为i的树深度大于等于j的概率。

那么会得到状态转移方程： g[i][j]=1/(i-1) * sigma(g[k][j-1]+g[i-k][j-1]) (k=1~i-1);

解释一下就是把i个叶子分给左右子树（当然左右都至少有一个叶子所以才是i-1种情况），然后加上根节点的深度要求左边的概率就是g[k][j-1]，右边的概率就是g[i-k][j-1]。但是这样会加多了（因为g[i][j]是没有区分左右的所以直接加，左右都满足条件的会加了两次），所以要减去相乘的结果。

至于这个方程最重要的一点是为什么结果能除以i-1？这个结论需要证明，建议看上面大佬或者洛谷大佬的题解证明过程。结论就是：

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 const int N=+;

 int q,n;

 double dp1[N];  //dp1[i]代表：i个结点的平均深度期望为dp1[i]

 void solve1() {

     dp1[]=;

     for (int i=;i<=n;i++) dp1[i]=dp1[i-]+/(double)i;

     printf("%.6lf\n",dp1[n]);

 }

 double dp2[N][N];  //dp2[i][j]代表：i个结点树深度大于等于j的概率

 void solve2() {

     dp2[][]=;

     for (int i=;i<=n;i++) {

         dp2[i][]=;

         for (int j=;j<=n;j++) {

             for (int k=;k<i;k++)

                 dp2[i][j]+=dp2[k][j-]+dp2[i-k][j-]-dp2[k][j-]*dp2[i-k][j-];

             dp2[i][j]/=(double)(i-);

         }

     }

     double ans=;

     for (int i=;i<n;i++) ans+=(dp2[n][i]-dp2[n][i+])*i;

     printf("%.6lf\n",ans);

 }

 int main()

 {

     cin>>q>>n;

     if (q==) solve1();

     else solve2();

     return ;

 }

巴特西

洛谷P3830 随机树（SHOI2012）概率期望DP

最新文章

热门文章