LP3830 [SHOI2012] 随机树 [期望/DP]
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 许可协议 进行许可☆