POJ 2096 Collecting Bugs：期望dp

题目链接：http://poj.org/problem?id=2096

题意：

　　有一个程序猿，他每天都会发现一个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:

 // state expression:

 // dp[i][j] = expectation

 // i: found i kinds of bug

 // j: in j different sys

 //

 // find the answer:

 // ans = dp[n][s]

 //

 // transferring:

 // 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

 //

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

 //

 // boundary:

 // dp[n][s] = 0

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 1005

 #define MAX_S 1005

 using namespace std;

 int n,s;

 double dp[MAX_N][MAX_S];

 void read()

 {

     cin>>n>>s;

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

     for(int i=n;i>=;i--)

     {

         for(int j=s;j>=;j--)

         {

             if(i==n && j==s) continue;

             double p1=(double)(n-i)/n*j/s;

             double p2=(double)i/n*(s-j)/s;

             double p3=(double)(n-i)/n*(s-j)/s;

             double p0=1.0-(double)i/n*j/s;

             dp[i][j]=(dp[i+][j]*p1+dp[i][j+]*p2+dp[i+][j+]*p3+)/p0;

         }

     }

 }

 void print()

 {

     printf("%.4f\n",dp[][]);

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

POJ 2096 Collecting Bugs：期望dp

最新文章

热门文章