Collecting Bugs POJ - 2096

题意

有\(n\)种病毒，\(s\)个系统，每次任意一个系统会得任意一种病毒，即在\(1 \sim n\)之间随机选一种病毒，在\(1 \sim s\)中选一台电脑，让这台电脑得这种病毒。

求每台电脑都得过病毒，每种病毒都有电脑染上过的期望次数。

分析

\(dp[i][j]\)表示已经有\(i\)种病毒出现过，\(j\)台电脑染上过病毒的期望次数。

明显\(dp[i][j]\)可以有四种转移。

1. \(dp[i][j] = (dp[i][j]+ 1) * (i/n) * (j/s)\)
2. \(dp[i + 1][j] = (dp[i][j]+1) * (n - i)/n * (j /s)\)
3. \(dp[i][j + 1] = (dp[i][j] + 1) * (i/n) * (s - j)/s\)
4. \(dp[i + 1][j + 1] = (dp[i][j] + 1) * (n - i)/n * (s - j)/s\)

但是这样不太好处理一开始的边界，我们变一下定义。

\(dp[i][j]\)表示已经有\(i\)种病毒出现过，\(j\)台电脑染上过病毒的状态到终止状态\(dp[n][s]\)期望次数。

转移变成:

\(dp[i][j] = ((dp[i][j] + 1) * i * j + (dp[i + 1][j] + 1） * (n - i) * j + （dp[i][j + 1] + 1） * i * (s - j) + (dp[i + 1][j + 1] + 1) * (n - i) * (s - j)) / (n * s)\)

把\(dp[i][j]\)当作未知数，解方程即可。

code

#include<iostream>
#include<cstdio>
using namespace std;
#define ld long double
int n,s; 
ld dp[1005][1005];
int main(){
    scanf("%d%d",&n,&s);
    for(int i = n; i >= 0; -- i) 
    for(int j = s; j >= 0; -- j){
    	if(i == n && j == s) continue;
    	//n * s * dp[i][j] = (dp[i + 1][j] * (n - i) * j + dp[i][j + 1] * i * (s - j) + dp[i + 1][j + 1] * (n - i) * (s - j) + dp[i][j] * i * j) ;
        dp[i][j] = (dp[i + 1][j] * (n - i) * j + dp[i][j + 1] * i * (s - j) + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j);
    }
    printf("%.10Lf\n",dp[0][0]);
	return 0;
}