zoj3822

这题说得是给了一个n*m的棋盘，每天在这个棋盘中放置一个棋子，不能放在之前已经摆放过得地方，求最后使得每行每列都有至少一个棋子的期望天数是多少，这样我们考虑怎么放，放哪里，显然数据大而且不知道状态怎么表示，考虑现在有i行j列放有k个棋子这样我们要求的概率就是dp[n][m][k],表示n行m列有棋子棋子个数为k

那么 dp[i][j][k] 会从 1扩展行 2扩展列 3 同时扩展行和列，4 行列都不扩展，相应的求出其概率

#include<map>

#include<set>

#include<list>

#include<cmath>

#include<ctime>

#include<deque>

#include<stack>

#include<queue>

#include<cstdio>

#include<bitset>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<ctype.h>

#include<complex>

#include<fstream>

#include<iomanip>

#include<numeric>

#include<sstream>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + ;

const double EPS = 1e-;

const int MAXN = 1e5 + ;

const int INF = 0x7fffffff;

const double PI = acos(-1.0);

typedef unsigned long long uLL;

int n, m, ans = -;

double dp[][][ * ];

int main()

{

    int cas;

    scanf("%d", &cas);

    while(cas--){

        int n, m;

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

        memset(dp, , sizeof(dp));

        dp[][][] = ;

        int cnt = n*m;

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

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

            for(int num = max(i, j); num <= i*j; ++num)

            {

                dp[i][j][num] += dp[i - ][j][num - ] * (n - i + )*j / (cnt - num + );

                dp[i][j][num] += dp[i][j - ][num - ] * (m - j + )*i / (cnt - num + );

                dp[i][j][num] += dp[i - ][j - ][num - ] * (cnt - (i - )*m - (j - )*n + (i - )*(j - )) / (cnt - num + );

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

                dp[i][j][num] += dp[i][j][num - ] * (i*j - num + ) / (cnt - num + );

            }

        double ans = ;

        int tt = n*m;// max(n*(m - 1) + 1, (n - 1)*m + 1);

        for(int i = ; i <= tt; ++i)

            ans += dp[n][m][i] * i;

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

    }

    return ;

}

相关文章