zoj 3822 Domination 概率dp 2014牡丹江站D题

Domination

---

Time Limit: 8 Seconds       Memory Limit: 131072 KB       Special Judge

---

Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboard with N rows and M columns.

Every day after work, Edward will place a chess piece on a random empty cell. A few days later, he found the chessboard was dominated by the chess pieces. That means there is at least one chess piece in every row. Also, there is at least one chess piece in every column.

"That's interesting!" Edward said. He wants to know the expectation number of days to make an empty chessboard of N × M dominated. Please write a program to help him.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There are only two integers N and M (1 <= N, M <= 50).

Output

For each test case, output the expectation number of days.

Any solution with a relative or absolute error of at most 10^-8 will be accepted.

Sample Input

2
1 3
2 2

Sample Output

3.000000000000
2.666666666667

题意：求保证n*m棋盘的每行每列都有棋子所用棋子的期望。

比赛的时候太紧张，居然随便弄了个2维dp的想法就开始写，写出来才反应到2维的没办法描述每种状态下的概率，然后马上改成三维，渣渣的概率公式又推错了！！确实是着急了。改了又改，还好最后过了··········庆幸之前做过概率dp的专题。第一场亚洲赛，可圈可点

思路：dp[i][j][k]表示用了i个棋子，有j行，k列被占时的期望，则放一个棋子有4中情况：

1、放在已有行，列之中

2、放在已有行，新的列之中

3、放在已有列，新的行里

4，放在新的行和列里

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

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

设每种状态的概率为pi，

转移方程：dp[i][j][k]=dp[i+1][j][k]*p1+dp[i+1][j+1][k]*p2+dp[i+1][j][k+1]*p3+dp[i+1][j+1][k+1]*p4+1;

其中：

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

怎么推的我就不说了，把放过的位置都统一到一侧，很简单，别的也没什么了，注意j*k>=i，概率dp求期望没做过很难解出来，但做过了这类题其实还真没有特别难的。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
double dp[2505][55][55];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        for(int i=n*m-1;i>=0;i--){
            for(int j=n;j>=0;j--){
                for(int k=m;k>=0;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+1][j][k]*p1+dp[i+1][j+1][k]*p2+dp[i+1][j][k+1]*p3+dp[i+1][j+1][k+1]*p4+1;
                }
            }
        }
        printf("%.10lf\n",dp[0][0][0]);
    }
    return 0;
}