首页 > 代码库 > 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 }
View Code

 

ZOJ3822 Domination(14牡丹江 D) 概率DP