题目链接
题解
dp[i][j]表示已经找到i种bug，并存在于j个子系统中，要达到目标状态的天数的期望。
显然，dp[n][s]=0，因为已经达到目标了。而dp[0][0]就是我们要求的答案。
dp[i][j]状态可以转化成以下四种：
dp[i][j] 发现一个bug属于已经找到的i种bug和j个子系统中-->p1 = ij / (ns)
dp[i+1][j] 发现一个bug属于新的一种bug，但属于已经找到的j种子系统-->p2 = (n-i)j / (ns)
dp[i][j+1] 发现一个bug属于已经找到的i种bug，但属于新的子系统-->p3 = i(s-j) / (ns)
dp[i+1][j+1]发现一个bug属于新的一种bug和新的一个子系统-->p4 = (n-i)(s-j) / (ns)
dp[i][j] = (sum 由XX转移来的期望)
发现dp[i][j]不能用dp[i][j] 更新，移项有去除dp[i][j]列转移方程
代码
#include<cstdio>
#include<algorithm>
inline int read() {
int x = 0;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x;
}
const int maxn = 1007;
int n,s;
double dp[maxn][maxn];
int main() {
n = read();s = read();
for(int i = n;i >= 0;-- i) {
for(int j = s;j >= 0;-- j) {
if(i == n && s == j) continue;
double p1 = 1.0 * i * j / (1.0 * n * s);
double p2 = 1.0 * (n - i) * j / (1.0 * n * s);
double p3 = 1.0 * i * (s - j) / (1.0 * n * s);
double p4 = 1.0 * (n - i) * (s - j) / (1.0 * n * s);
dp[i][j] = double (dp[i + 1][j] * p2 + dp[i][j + 1] * p3 + dp[i + 1][j + 1] * p4 + 1) / (1 - p1);
}
}
printf("%.4lf
",dp[0][0]);
return 0;
}