设为首页 加入收藏

TOP

zoj 3288 Domination (概率dp)
2015-07-20 17:29:54 来源: 作者: 【 】 浏览:3
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

评论

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

·Linux_百度百科 (2025-12-26 12:51:52)
·Shell 流程控制 | 菜 (2025-12-26 12:51:49)
·TCP/UDP协议_百度百科 (2025-12-26 12:20:11)
·什么是TCP和UDP协议 (2025-12-26 12:20:09)
·TCP和UDP详解 (非常 (2025-12-26 12:20:06)