zoj 3288 Domination (概率dp)

zoj 3288 Domination (概率dp)

///dp[i][j][k]表示i行j列已經有棋子，且放了k個的概率
///dp[i][j][k]一共有四種轉移方式
///1：dp[i-1][j][k-1]  概率為 (n-(i-1))*j/(n*m-(k-1))
///2:dp[i][j-1][k-1]   概率為  i*(m-(j-1))/(n*m-(k-1))
///3:dp[i-1][j-1][k-1]  概率為 (n-(i-1))*(m-(j-1))/(n*m-(k-1))
///4:dp[i][j][k-1]  概率為 (i*j-(k-1))/(n*m-(k-1))
# include 
# include 
# include 
# include 
using namespace std;
double  dp[55][55][2510];
int main()
{
    int n,m,t,i,j,k;
    double ans;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&n,&m);
            memset(dp,0,sizeof(dp));
            dp[0][0][0]=1;
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=m; j++)
                {
                    for(k=1; k<=n*m; k++)
                    {
                        if(i==n&&j==m)
                            dp[i][j][k]=dp[i-1][j][k-1]*(n-(i-1))*j/(n*m-(k-1))+dp[i][j-1][k-1]*i*(m-(j-1))/(n*m-(k-1))+dp[i-1][j-1][k-1]*(n-(i-1))*(m-(j-1))/(n*m-(k-1));
                        else
                            dp[i][j][k]=dp[i-1][j][k-1]*(n-(i-1))*j/(n*m-(k-1))+dp[i][j-1][k-1]*i*(m-(j-1))/(n*m-(k-1))+dp[i-1][j-1][k-1]*(n-(i-1))*(m-(j-1))/(n*m-(k-1))+dp[i][j][k-1]*(i*j-(k-1))/(n*m-(k-1));
                    }
                }
            }
            ans=0;
            for(i=1; i<=n*m; i++) ///求期望==概率乘天數的和集
                ans+=dp[n][m][i]*i;
            printf("%.12lf\n",ans);

        }
    }
    return 0;
}