首页 > 代码库 > zoj 3288 Domination (概率dp)
zoj 3288 Domination (概率dp)
///dp[i][j][k]表示i行j列已经有棋子,且放了k个的概率 ///dp[i][j][k]一共有四种转移方式 ///1:dp[i-1][j][k-1] 概率为 (n-(i-1))*j/(n*m-(k-1)) ///2:dp[i][j-1][k-1] 概率为 i*(m-(j-1))/(n*m-(k-1)) ///3:dp[i-1][j-1][k-1] 概率为 (n-(i-1))*(m-(j-1))/(n*m-(k-1)) ///4:dp[i][j][k-1] 概率为 (i*j-(k-1))/(n*m-(k-1)) # include <stdio.h> # include <algorithm> # include <string.h> # include <iostream> using namespace std; double dp[55][55][2510]; int main() { int n,m,t,i,j,k; double ans; while(~scanf("%d",&t)) { while(t--) { scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { for(k=1; k<=n*m; k++) { if(i==n&&j==m) dp[i][j][k]=dp[i-1][j][k-1]*(n-(i-1))*j/(n*m-(k-1))+dp[i][j-1][k-1]*i*(m-(j-1))/(n*m-(k-1))+dp[i-1][j-1][k-1]*(n-(i-1))*(m-(j-1))/(n*m-(k-1)); else dp[i][j][k]=dp[i-1][j][k-1]*(n-(i-1))*j/(n*m-(k-1))+dp[i][j-1][k-1]*i*(m-(j-1))/(n*m-(k-1))+dp[i-1][j-1][k-1]*(n-(i-1))*(m-(j-1))/(n*m-(k-1))+dp[i][j][k-1]*(i*j-(k-1))/(n*m-(k-1)); } } } ans=0; for(i=1; i<=n*m; i++) ///求期望==概率乘天数的和集 ans+=dp[n][m][i]*i; printf("%.12lf\n",ans); } } return 0; }
zoj 3288 Domination (概率dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。