Reviwe
T1:生物实验
你有\(n\)个瓶子,其中\(m\)瓶有毒,然后你有\(k\left(k\geqslant m\right)\) 只老鼠
每次每个瓶子只会有一只老鼠吃它!
每次有老鼠死后瓶子会被标记,以后不会再有老鼠去吃它了
问期望多少次可以把所有有毒的瓶子全部找到
对于\(100\%\)的数据有\(T \leqslant 1000, N \leqslant 500, M \leqslant 200, M\leqslant K \leqslant N\)
输入:
第一行是一个\(T\)
接下来\(T\)行每行三个正整数: \(n, m, k\)
输出:
一共有\(T\)行
对于每一组数据输出一行答案
题解:
\(DP[i]\)表示还剩下\(i\)瓶有毒的期望步数
那么这个可以构成一张\(DAG\)
因为\(i\) 这个点只能与比\(i\)小的点建一条有向边
既然已经知道有一张\(DAG\)了, 那么就可以拓扑逆向跑一边就可以得出答案了 \[ Dp[i] = \frac{\mathrm{C}_n^k}{\mathrm{C}_{n + i}^k}\times\left(Dp[i] + 1\right) + \sum\limits_{k=1}^i\frac{\mathrm{C}_n^{k-j}\cdot\mathrm{C}_m^j}{\mathrm{C}_{n+m}^k}\left(Dp[i-k] + 1\right) \]
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
const int Maxn(1e3 + 10);
int T, N, M, K;//N个瓶子, M瓶有毒, K只老鼠
int n, m, k;
double Dp[Maxn];//死了i只老鼠的期望步数
inline double C(int M, int N)
{
double Ans(1);
for (int i = 0; i < M; ++i) Ans *= double(N--) / double(M - i);
return Ans;
}
inline double C(int a, int b, int k)//C(k, a)/C(k, b)
{
double Ans(1.0);
Ans = double (C(k, a)) / double (C(k, b));
return Ans;
}
inline double C(int a, int b, int c, int j, int k)//C(k - j, a) * C(j, b) / C(k, c)
{
long double Ans(1.0);
Ans = double (C(k - j, a)) / double(C(k, c)) * double(C(j, b));
return Ans;
}
int main()
{
scanf ("%d\n", &T);
while (T--)
{
scanf ("%d %d %d", &N, &M, &K);
n = N - M;
for (int i = 1; i <= M; ++i)
{
k = min(K - M + i, n + i);
double P = C(n, n + i, k), Temp = 0;
for (int j = 1; j <= i; ++j) Temp += (Dp[i - j] + 1.0) * C(n, i, n + i, j, k);
Dp[i] = (Temp + P) / (1.0 - P);
}
printf ("%.2lf\n", Dp[M]);
}
system("pause");
}