题目链接：

题意：

　　有一个程序猿，他每天都会发现一个bug。

　　bug共有n个种类。属于某一个种类的概率为1/n。

　　有s个子系统，每个bug属于一个系统。属于某一个系统的概率为1/s。

　　问你发现的bug能够覆盖到n个种类和s个系统的期望天数。

 

题解：

　　期望dp转移的套路：

　　　　倒着推。

　　　　利用性质：期望 = ∑ (P（子期望）*φ（子期望）)

 

　　状态表示：

　　　　dp[i][j] = expectation

　　　　i：覆盖到i个种类

　　　　j：覆盖到j个系统

　　　　dp：从当前状态到达目标状态的期望天数（此状态的剩余天数）

 

　　如何转移：

　　　　套路。先考虑它能够转移到的子期望。

　　　　now: dp[i][j]

　　　　四种转移：

　　　　　　（1）dp[i][j]：bug的没有覆盖新的区域。概率p0' = (i/n)*(j/s)

　　　　　　（2）dp[i+1][j]：bug为新种类，不是新系统。概率p2 = (n-i)/n * j/s.

　　　　　　（3）dp[i][j+1]：bug不是新种类，是新系统。概率p3 = i/n * (s-j)/s.

　　　　　　（4）dp[i+1][j+1]：既是新种类，又是新系统。概率p4 = (n-i)/n*(s-j)/s

　　　　利用期望性质：

　　　　　　dp[i][j] = dp[i][j]*(i/n)*(j/s)

　　　　　　　　　　　　+ dp[i+1][j]*((n-i)/n)*(j/s)

　　　　　　　　　　　　+ dp[i][j+1]*(i/n)*((s-j)/s)

　　　　　　　　　　　　+ dp[i+1][j+1]*((n-i)/n)*((s-j)/s)

　　　　　　　　　　　　+ 1

　　　　因为找到一个bug意味着过去了一天，所以dp[i][j]最后要+1。

　　　　移项：

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

　　　　　　　　　　　　+ dp[i][j+1]*(i/n)*((s-j)/s)

　　　　　　　　　　　　+ dp[i+1][j+1]*((n-i)/n)*((s-j)/s) + 1)

　　　　　　　　　　　　/ (1 - (i/n)*(j/s))

 

　　边界条件：

　　　　达到目标状态时，剩余天数为0。

　　　　dp[n][s] = 0

 

AC Code:

1 // state expression: 2 // dp[i][j] = expectation 3 // i: found i kinds of bug 4 // j: in j different sys 5 // 6 // find the answer: 7 // ans = dp[n][s] 8 // 9 // transferring:10 // dp[i][j] = dp[i][j]*(i/n)*(j/s)11 //            + dp[i+1][j]*((n-i)/n)*(j/s)12 //            + dp[i][j+1]*(i/n)*((s-j)/s)13 //            + dp[i+1][j+1]*((n-i)/n)*((s-j)/s) + 114 //15 // dp[i][j] = (dp[i+1][j]*((n-i)/n)*(j/s)16 //            + dp[i][j+1]*(i/n)*((s-j)/s)17 //            + dp[i+1][j+1]*((n-i)/n)*((s-j)/s) + 1)18 //            / (1 - (i/n)*(j/s))19 //20 // boundary:21 // dp[n][s] = 022 #include 
     
      23 #include 
      
       24 #include 
       
        25 #define MAX_N 100526 #define MAX_S 100527 28 using namespace std;29 30 int n,s;31 double dp[MAX_N][MAX_S];32 33 void read()34 {35     cin>>n>>s;36 }37 38 void solve()39 {40     memset(dp,0,sizeof(dp));41     for(int i=n;i>=0;i--)42     {43         for(int j=s;j>=0;j--)44         {45             if(i==n && j==s) continue;46             double p1=(double)(n-i)/n*j/s;47             double p2=(double)i/n*(s-j)/s;48             double p3=(double)(n-i)/n*(s-j)/s;49             double p0=1.0-(double)i/n*j/s;50             dp[i][j]=(dp[i+1][j]*p1+dp[i][j+1]*p2+dp[i+1][j+1]*p3+1)/p0;51         }52     }53 }54 55 void print()56 {57     printf("%.4f\n",dp[0][0]);58 }59 60 int main()61 {62     read();63     solve();64     print();65 }