poj 2096(概率期望DP)

poj 2096
设$dp(i, j)$为已经发现了$i$类bug,$j$个系统中发现了bug时要到达目标的天数期望。
明显$dp(n, s)=0$,因为已经到达了目标,所以这题要倒推,期望DP一般都要倒推来做,因为已知终态。
那么$dp(i,j)$可以由$4$个状态转移:
$dp(i+1,j+1)$, 这个bug不在已经找到的类型中,也不在已经找到bug的系统中,概率为$(1-\frac{i}{n})(1-\frac{j}{s})=\frac{(n-i)(s-j)}{ns}$(通分处理一下,这样减少除法,减小精度误差)
$dp(i+1,j)$, 这个bug不在已经找到的类型中,但在已经找到bug的系统中,概率为$(1-\frac{i}{n})\frac{j}{s}=\frac{(n-i)j}{ns}$
$dp(i,j+1)​$, 这个bug在已经找到的类型中,但不在已经找到bug的系统中,概率为$\frac{i}{n}(1-\frac{j}{s})=\frac{i(s-j)}{ns}​$
$dp(i,j)$, 这个bug不在已经找到的类型中,也不在已经找到bug的系统中,概率为$\frac{ij}{ns}$
然后根据期望运算的线性性质,得到转移方程:
$dp(i,j)=dp(i+1,j+1) \times \frac{(n-i)(s-j)}{ns} + dp(i+1,j) \times \frac{(n-i)j}{ns}$
$+ dp(i,j+1) \times \frac{i(s-j)}{ns} + dp(i,j) \times \frac{i(s-j)}{ns}+1$
其中$+1$是本次转移,就是从其他四个状态转移转移到本状态的花费。
把右边的$dp(i,j)$移到左边,有$dp(i,j)=\frac{dp(i+1,j+1) \times \frac{(n-i)(s-j)}{ns} + dp(i+1,j) \times \frac{(n-i)j}{ns} + dp(i,j+1) \times \frac{i(s-j)}{ns} +1}{1-\frac{ij}{ns}}$
然后发现有分母下都有$ns$,那么上下乘$ns$,得$dp(i,j)=\frac{dp(i+1,j+1) \times (n-i)(s-j) + dp(i+1,j) \times (n-i)j + dp(i,j+1) \times i(s-j) +ns}{ns-ij}$
经过转换,除法只有一个了,大大减小精度误差,接着倒推求解就行了,答案是$dp(0,0)$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int n, s;
db dp[MAXN][MAXN];
void clean() {
ms(dp, 0);
}
void solve() {
clean();
for (int i=n;i>=0;i--) {
for (int j=s;j>=0;j--) {
if (i==n && j==s) continue;
dp[i][j] = (db)(n*s + dp[i+1][j+1]*(n-i)*(s-j) + dp[i+1][j]*(n-i)*j + dp[i][j+1]*i*(s-j))/(db)(n*s - i*j);
}
}
printf("%.4f", dp[0][0]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &s)==2) solve();
return 0;
}
------ 本文结束 ------