ACM模版

描述

题解

寻找 n 种 bug 且 s 个子系统均有波及的期望。

设 dp[i][j] 表示已经找到了 i 种 bug ，并且已经波及到了 j 个子系统的期望。

所以， dp[n][s]=0.0 ，而 dp[0][0] 则是我们要求的答案。

由题可知， dp[i][j] 可以转化为以下四种：

  1. dp[i][j] 发现一个已经找到的 bug 并且位于已经波及的子系统中
  2. dp[i+1][j] 发现一个未找到的 bug 并且位于已经波及的子系统中
  3. dp[i][j+1] 发现一个已经找到的 bug 并且位于未波及的子系统中
  4. dp[i+1][j+1 发现一个未找到的 bug 并且位于未波及的子系统中

以上四种状态对应的概率分别为：

  1. p1=i∗jn∗s
  2. p2=(n−i)∗jn∗s
  3. p3=i∗(s−j)n∗s
  4. p4=(n−i)∗(s−j)n∗s

正如 kuangbin 大佬所说的那样概率 DP 一般正着是求概率，逆着是求期望。

所以，

dp[i][j]=p1∗dp[i][j]+p2∗dp[i+1][j]+p3∗dp[i][j+1]+p4∗dp[i+1][j+1]+1

这里 +1 是因为每次都多一天。

整理可得，

dp[i][j]=(n∗s+(n−i)∗j∗dp[i+1][j]+i∗(s−j)∗dp[i][j+1]+(n−i)∗(s−j)∗dp[i+1][j+1])/ (n∗s−i∗j)

这个题十分的玄学，用 G++WA ，用 C++AC 。

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1e3 + 10;

int n, s;
double dp[MAXN][MAXN];

int main(int argc, const char * argv[])
{
    cin >> n >> s;

    int t = n * s;
    dp[n][s] = 0.0;
    for (int i = n; i >= 0; i--)
    {
        for (int j = s; j >= 0; j--)
        {
            if (i == n && j == s)
            {
                continue;
            }
            dp[i][j] = (t
                     + (n - i) * j * dp[i + 1][j]
                     + i * (s - j) * dp[i][j + 1]
                     + (n - i) * (s - j) * dp[i + 1][j + 1])
                     / (t - i * j);
        }
    }
    printf("%.4lf\n", dp[0][0]);

    return 0;
}