本文主要是介绍zoj 3822 (2014 牡丹江区域赛 D) Domination，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个n*m的棋盘，每天等概率随机在一个空位上放一个棋子，直到每行每列都至少有一个棋子。问这个过程持续天数的期望。
思路：概率dp。如果想到了如何表示状态，剩下的就不难了。dp(i,j,k)表示出现 i行中有棋子，j列中有棋子，一共有k个棋子 这种情况的概率。其中i=0~n，j=0~m，k=0~n*m-min(n,m)+1。初态是dp(0,0,0)=1.0。状态转移有4种情况，即放下棋子后没有新增的行列，仅增加行，仅增加列，同时增加行列，具体状态转移见代码。最后按照期望的定义算一下即可。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#include <sstream>
#define INF 1000000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010 using namespace std; double dp[52][52][2510];int main(){int n,m;int t; cin>>t;while(t--){cin>>n>>m;//initfor(int k=0;k<=n*m;k++){for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j][k]=0.0;}}}dp[0][0][0]=1.0;//double ans=0.0;int end=n*m-min(n,m)+1;for(int k=0;k<=end;k++){for(int i=0;i<n;i++){for(int j=0;j<m;j++){dp[i+1][j+1][k+1]+=dp[i][j][k]*(n*m-i*m-j*n+i*j)/(n*m-k);dp[i+1][j+1][k+1]+=dp[i][j+1][k]*( (n-i)*(j+1) )/(n*m-k);dp[i+1][j+1][k+1]+=dp[i+1][j][k]*( (m-j)*(i+1) )/(n*m-k);if(!(i+1==n&&j+1==m))dp[i+1][j+1][k+1]+=dp[i+1][j+1][k]*((i+1)*(j+1)-k)/(n*m-k);else ans+=dp[n][m][k]*k;}}}printf("%.10lf\n",ans);}return 0;
}
这篇关于zoj 3822 (2014 牡丹江区域赛 D) Domination的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
