【BZOJ2830/洛谷3830】随机树(动态规划)
规划 动态 随机 洛谷
2023-09-11 14:14:41 时间
【BZOJ2830/洛谷3830】随机树(动态规划)
题面
题解
先考虑第一问。
第一问的答案显然就是所有情况下所有点的深度的平均数。
考虑新加入的两个点,一定会删去某个叶子,然后新加入两个深度为原先叶子\(+1\)的点。
那么新加入的叶子的深度的期望是未加入之前的期望+1,假设\(f_i\)为\(i\)个点的期望。
那么\(f_i=(f_{i-1}*({i-1})-f_{i-1}+2*(f_{i-1}+1))/i=f_{i-1}+2/i\)
含义就是平均的深度乘上点的个数等于深度总和,减去删去的点的深度,加入两个新的深度为原先点\(+1\)的点。
考虑第二问
不难想到一个状态\(f[i][j]\)表示拥有\(i\)个节点,深度为\(j\)的概率。
那么答案就是\(\sum_{i=0}^nf[n][i]*i\)
这个转移不难,我们根节点已经固定,并且它一定拥有左右子树,我们转移的时候分开考虑左右子树,然后再在根节点的位置合并,即
\[f[i][max(k,l)+1]\rightarrow f[j][k]*f[i-j][l]/(i-1)
\]
除掉\(i-1\)的原因是一开始我们直接把左右儿子都当成整棵树来看,所以最终合并的时候要把总方案除掉。
还有一种做法,大同小异,然而复杂度更优秀。
设\(f[i][j]\)表示\(i\)个叶子的树,深度至少为\(j\)的概率。
转移和上面的东西类似,容斥去重。
\[f[i][j]=\frac{1}{i-1}\sum f[k][j-1]*1+f[i-k][j-1]*1-f[i][j-1]*f[i-k][j-1]
\]
答案是\(\sum f[n][i]\)
#include<iostream>
#include<cstdio>
using namespace std;
int n,Q;
double ans,f[101][101];
int main()
{
cin>>Q>>n;
if(Q==1)
{
for(int i=2;i<=n;++i)
ans+=2.0/i;
printf("%.6lf\n",ans);
}
else
{
for(int i=1;i<=n;++i)f[i][0]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=i;++j)
for(int k=1;k<i;++k)
f[i][j]+=(f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1])/(i-1);
for(int i=1;i<=n;++i)ans+=f[n][i];
printf("%.6lf\n",ans);
}
return 0;
}
相关文章
- 【BZOJ5314】[JSOI2018]潜入行动(动态规划)
- 【BZOJ1560】[JSOI2009]火星藏宝图(贪心,动态规划)
- 【arc093f】Dark Horse(容斥原理,动态规划,状态压缩)
- 【BZOJ4903】【UOJ#300】吉夫特(卢卡斯定理,动态规划)
- 【BZOJ3294】放棋子(动态规划,容斥,组合数学)
- 【Luogu3478】【POI2008】STA-Station(动态规划)
- 【BZOJ1087】【SCOI2005】互不侵犯(状态压缩,动态规划)
- 【Luogu1879】玉米田(状态压缩,动态规划)
- 【BZOJ4476】[Jsoi2015]送礼物 分数规划+RMQ
- 斐波那契数列:暴力递归改动态规划
- C#,动态规划(DP)N皇后问题(N Queen Problem)的回溯(Backtracking)算法与源代码
- 阿里感悟 (十七)- 计划和规划能力
- 动态规划(DP)之多边形游戏问题
- 动态规划实例
- 【蓝桥杯Java组】带你刷爆常见动态规划模型
- 170、【动态规划】leetcode ——188. 买卖股票的最佳时机 IV:二维数组+一维数组 (C++版本)
- 157、【动态规划】leetcode ——377. 组合总和 Ⅳ:二维数组+一维滚动数组(C++版本)
- 猿创征文 |【算法面试入门必刷】动态规划-线性dp(四)
- 在动态规划的海洋中遨游(二)
- 动态规划-01背包问题(纯01背包、分割等和子集、最后一块石头的重量II、目标和、一和零)
- 【JAVA】初识动态规划
- zoj2676 Network Wars(0-1分数规划,最大流模板)
- nyoj 49-开心的小明(动态规划, 0-1背包问题)
- 【算法专题】动态规划的理论与实战
- 西北区域新能源发展规划及运行监管报告:弃光弃风依然严重
- Zipper(动态规划)
- Python实现采药问题(+动态规划简单概述)