zoj 3822 && 牡丹江d题

dp水题，dp[i][j][d]表示第d天共有i行，j列被排掉，原来共有m行n列：导出公式：dp[i][j][d]=dp[i-1][j][d-1]*(m-i+1)*)j/(m*n-d+1)+dp[i][j-1][d-1]*(n-j+1)*i/(m*n-d+1)+dp[i-1][j-1][d-1]*(m-i+1)*(n-j+1)/(m*n-d+1)+dp[i][j][d-1]*(i*j-d+1)/(m*n-d+1)；

下面是ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
double  dp[51][51][2501];
int n,m;

void init()
{
        for(int i=0;i<=max(m,n);i++)
        {
            for(int j=0;j<=(max(m,n))*(max(m,n));j++)
            {
                dp[0][i][j]=dp[i][0][j]=0;
            }
        }
        dp[0][0][0]=dp[1][1][1]=1;
}

int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
        scanf("%d%d",&m,&n);
         init();
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int d=max(i,j);d<=i*j;d++)
                {
                    double x=(double) (m-i+1),y=(double)(n-j+1),z=(double)(m*n-(d-1));
                    dp[i][j][d]=dp[i-1][j][d-1]*x*((double) (j))/z+dp[i][j-1][d-1]*y*((double)(i))/z+dp[i-1][j-1][d-1]*x*y/z+dp[i][j][d-1]*((double)(i*j-d+1))/z;
                }
            }
        }
        double ans=0;
        for(int i=max(m,n);i<=m*n;i++)
        {
            ans+=(dp[m][n][i]-dp[m][n][i-1])*((double)(i));
        }
        printf("%.12lf
",ans);
    }
    return 0;
}