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

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

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 
#include 
#include 
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