首页 > 代码库 > zoj3822

zoj3822

2024-07-27 18:43:02   212人阅读

这题说得是给了一个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 + 7;const double EPS = 1e-9;const int MAXN = 1e5 + 5;const int INF = 0x7fffffff;const double PI = acos(-1.0);typedef unsigned long long uLL;int n, m, ans = -1;double dp[55][55][55 * 50];int main(){    int cas;    scanf("%d", &cas);    while(cas--){        int n, m;        scanf("%d%d", &n, &m);        memset(dp, 0, sizeof(dp));        dp[1][1][1] = 1;        int cnt = n*m;        for(int i = 1; i <= n; ++i)            for(int j = 1; j <= m; ++j)            for(int num = max(i, j); num <= i*j; ++num)            {                dp[i][j][num] += dp[i - 1][j][num - 1] * (n - i + 1)*j / (cnt - num + 1);                dp[i][j][num] += dp[i][j - 1][num - 1] * (m - j + 1)*i / (cnt - num + 1);                dp[i][j][num] += dp[i - 1][j - 1][num - 1] * (cnt - (i - 1)*m - (j - 1)*n + (i - 1)*(j - 1)) / (cnt - num + 1);                if(i==n&&j==m) continue;                dp[i][j][num] += dp[i][j][num - 1] * (i*j - num + 1) / (cnt - num + 1);            }        double ans = 0;        int tt = n*m;// max(n*(m - 1) + 1, (n - 1)*m + 1);        for(int i = 1; i <= tt; ++i)            ans += dp[n][m][i] * i;        printf("%.12lf\n", ans);    }    return 0;}
View Code

 

zoj3822


联系
我们