zoj 3822 Domination (概率dp 天数期望)

参考博客：http://blog.csdn.net/napoleon_acm/article/details/40020297

题意：给定n*m的空棋盘

每一次在上面选择一个空的位置放置一枚棋子，直至每一行每一列都至少有一个棋子，求放置次数的期望

分析：

dp[i][j][k] 表示当前用了<=k个chess ,覆盖了i行j列(i*j的格子每行至少一个，每列至少一个)的概率。

dp[i][j][k] 由 dp[i][j][k-1] , dp[i-1][j][k-1], dp[i][j-1][k-1], dp[i-1][j-1][k-1]得到，分别表示添加的新的一个chess, 不覆盖新的行列，只新覆盖一行，只新覆盖一列，同时新覆盖一行和一列,得到dp[i][j][k]。
递推时，每个概率 * (可以覆盖的点数/剩余所有的空点数) 相加得到[i][j][k].

ans += (dp[n][m][i] - dp[n][m][i-1])* i； (i = [1, n*m])

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #define LL __int64

 const int maxn = +;

 using namespace std;

 double d[maxn][maxn][];

 int main()

 {

     double ans;

     int t, i, j, k, n, m;

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

         memset(d, , sizeof(d));

         d[][][] = ;

         for(i = ; i <= n; i++)

         for(j = ; j <= m; j++)

         for(k = ; k <= n*m; k++)

         {

             int sum = n*m-k+;

             d[i][j][k] = d[i][j][k-]*((i*j-k+)*1.0/sum*1.0)+  //因为这里还加上了已经覆盖了i行j列的概率，所以dp[i][j][k] 表示当前用了<=k个chess ,覆盖了i行j列(i*j的格子 每行至少一个，每列至少一个)的概率。

             d[i-][j][k-]*(j*(n-i+)*1.0/sum*1.0)+

             d[i][j-][k-]*(i*(m-j+)*1.0/sum*1.0)+

             d[i-][j-][k-]*((n-i+)*(m-j+)*1.0/sum*1.0);

         }

         ans = ;

         for(i = ; i <= n*m; i++)

         ans += (d[n][m][i]-d[n][m][i-])*i;  //减去表示用i个棋子覆盖的概率。

         printf("%.12lf\n", ans);

     }

     return ;

 }

做了后一道概率dp，发现也可以用期望你逆推的方法。

可参照博客：http://blog.csdn.net/smz436487/article/details/40049189

初始化：dp[i][n][m]=0;(0<=i<=n*m)

dp[0][0][0]就是答案。

2维的没办法描述每种状态下的概率

代码：

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 double dp[][][];

 int main()

 {

     int t,n,m;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m);

         memset(dp,,sizeof(dp));

         for(int i=n*m-;i>=;i--){

             for(int j=n;j>=;j--){

                 for(int k=m;k>=;k--){

                     if(j==n&&k==m)continue;

                     if(j*k<i)continue;

                     double p1,p2,p3,p4;

                     p1=1.0*(j*k-i)/(n*m-i);

                     p2=1.0*(n-j)*k/(n*m-i);

                     p3=1.0*(m-k)*j/(n*m-i);

                     p4=1.0*(n-j)*(m-k)/(n*m-i);

                     dp[i][j][k]=dp[i+][j][k]*p1+dp[i+][j+][k]*p2+dp[i+][j][k+]*p3+dp[i+][j+][k+]*p4+;

                 }

             }

         }

         printf("%.10lf\n",dp[][][]);

     }

     return ;

 }

巴特西

zoj 3822 Domination (概率dp 天数期望)

最新文章

热门文章