首页 > 代码库 > ZOJ3822 Domination(14牡丹江 D) 概率DP
ZOJ3822 Domination(14牡丹江 D) 概率DP
题意:给你一个N×M的棋盘,每一次随机在这里放一个子(不能重复)问你最后每一行每一列只要有一个子的期望次数
解题思路:dp[i][j][s] 已经用 i 个子 占了 j 行 s 列的概率,再找出状态转移方程就行。
解题代码:
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月18日 星期六 10时19分16秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 double dp[3000][52][52];28 int n, m;29 double solve(int x,int y,int z)30 {31 32 }33 void print()34 {35 for(int i = 1;i <= n*m ;i ++)36 {37 for(int j = 1; j <= n+1;j ++)38 {39 for(int s = 1; s<= m+1; s ++)40 { printf("%lf ",dp[i][j][s]);41 }42 printf("\n");43 }44 printf("\n");45 }46 47 }48 int main(){49 int t; 50 scanf("%d",&t);51 while(t--)52 {53 scanf("%d %d",&n,&m);54 if(n > m )55 swap(n,m);56 memset(dp,0,sizeof(dp));57 dp[1][1][1] = 1.0 ;58 for(int i = 2;i <= n*m ;i ++)59 {60 for(int j = 1; j <= n;j ++)61 {62 for(int s = 1; s<= m; s ++)63 {64 int k = (n*m-(i-1));65 if(!(j == n && s ==m))66 dp[i][j][s] += dp[i-1][j][s]*(max(0,j*s-(i-1))*1.0/k); 67 dp[i][j][s+1] += dp[i-1][j][s] *(max(0,j*m-s*j)*1.0/k); 68 dp[i][j+1][s] += dp[i-1][j][s] *(max(0,s*n-s*j)*1.0/k);69 dp[i][j+1][s+1] += dp[i-1][j][s] *((n*m-(s*n+j*m-s*j))*1.0/k);70 }71 }72 }73 //print(); 74 double ans = 0.0 ; 75 for(int i = 1;i <= n*m ;i ++)76 ans += i * dp[i][n][m];77 printf("%.10lf\n",ans);78 }79 return 0;80 }
ZOJ3822 Domination(14牡丹江 D) 概率DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。