设为首页 加入收藏

TOP

zoj 3288 Domination (概率dp)
2015-07-20 17:29:54 来源: 作者: 【 】 浏览:2
Tags:zoj 3288 Domination 概率
///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 
  
   
# include 
   
     # include 
    
      # include 
     
       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; } 
     
    
   
  

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇Codeforces 110B-Lucky String(.. 下一篇POJ LAKE COUNTING 2386

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·Bash 脚本教程——Li (2025-12-26 07:53:35)
·实战篇!Linux shell (2025-12-26 07:53:32)
·整理了250个shell脚 (2025-12-26 07:53:29)
·HyperText Transfer (2025-12-26 07:20:48)
·半小时搞懂 HTTP、HT (2025-12-26 07:20:42)