poj 2096(概率期望DP)

发表于 | 分类于 | | + s

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)$

#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;
}
------ 本文结束 ------