题意：在一个n*m的棋盘上放棋子，一个棋子可覆盖一行一列，若n行m列全被覆盖则停止放棋子，求棋子的期望
思路：期望DP， dp[i][j][k]表示放了i个棋子覆盖了j行k列
已知dp[0][0][0]=1,求dp[1~n*m][n][m]
四种情况：
1.再放一个棋子，行列都不增加
dp[i+1][j][k]+=dp[i][j][k]*(j*k-i)*1.0/(m*n-i);
2.只增加一行
dp[i+1][j+1][k]+=dp[i][j][k]*(n-j)*k*1.0/(m*n-i);
3.只增加一列
dp[i+1][j][k+1]+=dp[i][j][k]*(m-k)*j*1.0/(m*n-i);
4.增加了一行一列
dp[i+1][j+1][k+1]+=dp[i][j][k]*((m-k)*(n-j))*1.0/(m*n-i);
#include <iostream> #include <queue> #include <stack> #include <vector> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <cstdio> using namespace std; double dp[2505][55][55]; int main() { int T,n,m,i,j,k; double ans; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); dp[0][0][0]=1.0; for(i=0;i<=n*m;i++) { for(j=0;j<=n;j++) { for(k=0;k<=m;k++) { if(j==n&&k==m) continue; dp[i+1][j][k]+=dp[i][j][k]*(j*k-i)*1.0/(m*n-i); dp[i+1][j+1][k]+=dp[i][j][k]*(n-j)*k*1.0/(m*n-i); dp[i+1][j][k+1]+=dp[i][j][k]*(m-k)*j*1.0/(m*n-i); dp[i+1][j+1][k+1]+=dp[i][j][k]*((m-k)*(n-j))*1.0/(m*n-i); } } } ans=0; for(i=0;i<=n*m;i++) ans+=i*dp[i][n][m]; printf("%.8f ",ans); } return 0; }