題目描述
給你一個\(n\times m\)的棋盤，每次隨機在棋盤上放一個國際象棋中的車，不能和以前放的重疊。每個車可以控制當前行和當前列。當所有行和所有列都被控制時結束游戲。問你結束時期望放了多少個車。
注意：結束的條件是所有行和所有列都被控制，而不是所有格子都被控制。
\(n,m\leq 50\)
題解
簡單DP
\(f_{i,j,k}\)表示放了\(k\)個車后控制了\(i\)行\(j\)列的概率
\[ f_{i,j,k}=\frac{f_{i,j,k-1}\times(ij-(k-1))+f_{i,j-1,k-1}\times i(m-j+1)+f_{i-1,j,k-1}\times j(n-i+1)+f_{i-1,j-1,k-1}\times(n-i+1)(m-j+1)}{nm-k+1} \]
答案是
\[ \sum_{i=1}^{nm}i(f_{n,m,i}-f_{n,m,i-1}) \]
弄個滾動數組搞一下
時間復雜度：\(O(n^4)\)
代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
double f[2][60][60];
void solve()
{double ans=0;int n,m;scanf("%d%d",&n,&m);memset(f,0,sizeof f);int i,j,k;f[0][0][0]=1;int t=0;for(k=1;k<=n*m;k++){t^=1;double now=1./(n*m-k+1);memset(f[t],0,sizeof f[t]);for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[t][i][j]=(f[t^1][i][j]*(i*j-k+1)+f[t^1][i-1][j]*(n-i+1)*j+f[t^1][i][j-1]*i*(m-j+1)+f[t^1][i-1][j-1]*(n-i+1)*(m-j+1))*now;ans+=k*(f[t][n][m]-f[t^1][n][m]);}printf("%.10lf\n",ans);
}
int main()
{int t;scanf("%d",&t);while(t--)solve();return 0;
}
