Problem

https://www.luogu.org/problemnew/show/P3830

Solution

联动：https://pst.iorinn.moe/archives/sol-usaco-nocows.html

第一问求可能的深度期望总和。

$f_{i,j}$ 现深度为 i，剩 j 次展开的深度期望和。方程略。

第二问求最深深度期望。

$f_{i,j}$ 深度一定为 i，剩 j 次展开的树的概率。
$S_{i,j}$ 深度 $\leq i$，剩 j 次展开的树的概率。

左右子树分配展开数一共有 $j$ 种可能，由乘法和加法原理有：
$$f_{i,j} =\frac{1}{j} \sum_{x=0}^{j-1} f_{i-1, j-1-x}*(2S_{i-2,x}+f_{i-1, x})$$

$S$ 就是前缀和。

$f_{0,0}=1$。

考虑一次转移，我们令左子树 $k$ 次展开，右子树 $j-k$ 次展开。考虑这样子情况下的分配合法概率。

分配展开的概率相同，为 $\frac {1}{j}$，因此根据全概率公式有如上的 dp 方程。

Code

// Code by ajcxsu
// Problem: random_tree

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=110;
int q, n;

namespace solve1 {
    double f[N][N];
    char vis[N][N];
    double dfs(int i, int j) {
        if(j==0) return i;
        if(vis[i][j]) return f[i][j];
        vis[i][j]=1;
        for(int k=0;k<=j-1;k++) f[i][j]+=dfs(i+1, k)+dfs(i+1, j-1-k);
        return f[i][j]/=j;
    }
    void work() {
        cout<<dfs(0, n-1)/n<<endl;
    }
}

namespace solve2 {
    double f[N][N], f3[N][N];
    char vis[N][N], vis2[N][N];
    double dp(int, int);
    double S(int, int);
    double dp(int x, int y) {
        if(x==0) return y==0;
        if(y<x) return 0;
        if(vis[x][y]) return f[x][y];
        f[x][y]=0, vis[x][y]=1;
        for(int i=0;i<=y-1;i++)
            f[x][y]=f[x][y]+dp(x-1, y-i-1)*(S(x-2, i)*2+dp(x-1, i));
        return f[x][y]/=y;
    }
    double S(int x, int y) {
        if(x<0) return 0;
        if(vis2[x][y]) return f3[x][y];
        f3[x][y]=0, vis2[x][y]=1;
        for(int i=0;i<=x;i++) f3[x][y]+=dp(i, y);
        return f3[x][y];
    }
    double cnt[N], tot;
    void work() {
        double ans=0;
        for(int i=1;i<=n-1;i++)
            ans+=1.0*i*(cnt[i]=dp(i, n-1));
        cout<<ans<<endl;
        return;
    }
}

int main() {
    cout.setf(ios::fixed), cout<<setprecision(6);
    cin>>q>>n;
    if(q==1) solve1::work();
    else solve2::work();
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3830.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆