P3830-[SHOI2012]随机树
题目:
题目描述:
输入格式:
输入仅有一行，包含两个正整数 q, n，分别表示问题编号以及叶结点的个数。
输出格式:
输出仅有一行，包含一个实数 d，四舍五入精确到小数点后 6 位。如果 q = 1，则 d 表示叶结点平均深度的数学期望值；如果 q = 2，则 d 表示树深度的数学期望值。
样例:
样例输入 1:
样例输出 1:
样例输入 2:
样例输出 2:
样例输入 3:
样例输出 3:
样例输入 4:
样例输出 4:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include "ybwhead/ios.h"
const int maxn = 2e3 + 10;
double f[maxn][maxn];
int q, n;
int main()
{
yin >> q >> n;
if (q == 1)
{
double x = 0;
for (int i = 2; i <= n; i++)
x = x + (double)2 / i;
yout << x << endl;
return 0;
}
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];
// yout << i << " " << j << ' ' << f[i][j] << endl;
f[i][j] = f[i][j] / (i - 1);
}
}
double ans = 0;
for (int i = 1; i < n; i++)
ans += f[n][i];
yout << ans << endl;
return 0;
}
|
