概率dp的边界处理 POJ 2096

题目地址：https://vjudge.net/problem/POJ-2096

说的是有n个bug，和s个系统。现在一个人一天能发现一个bug，它可能是任何一个系统中的，也可能会发现已经发现过的bug。

问，他发现全部n个bug，并且s个系统中都出现bug的天数的期望。

代码是借用kuangbin大神的：

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 const int MAXN=;

 double dp[MAXN][MAXN];

 int main()

 {

     int n,s;

     while(scanf("%d%d",&n,&s)!=EOF)

     {

         dp[n][s]=;

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

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

           {

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

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

           }

         printf("%.4lf\n",dp[][]);//POJ上G++要改成%.4f

     }

     return ;

 }

关于转移方程，有什么不懂的可以移步 https://www.cnblogs.com/Paul-Guderian/p/7624039.html#undefined

没什么好说的，我这只弱鸡都能看懂。。。

但我觉得需要注意的地方是代码的第18行和19行，对边界的处理，可以说没有一点多余啊。。。

注意到dp过程是从右下角(dp[n][s]) 开始的，决定当前位置的值是它右、下、以及右下位置的值

那么左边、上边的边界自然不用考虑，可能出现溢出的位置就剩下右边，下边，以及右下角。

我们注意到程序仅在第18行处理了右下角，是不是kuangbin大神漏掉了右边和下边的处理呢？

不，事实上右边和下边的处理在计算概率的时候就已经完成了!

就拿下边来说，注意到，当且仅当 i==n 时，访问 dp[i+1][j] 时会在下边越界。

但是，注意到与这一项相乘的概率恰好包括了 (n-i) 这一因子。

因此，越界访问得到的数据( dp[n+1][j] )并不会影响 dp[i][j] 的计算结果。

可能很简单。。。

但是对我这样的弱鸡来说，我觉得挺神奇的，求大犇们勿喷。。。

巴特西

概率dp的边界处理 POJ 2096

最新文章

热门文章