首页 > 代码库 > zoj--3822--第二题概率dp

zoj--3822--第二题概率dp

这题 比上次那个概率dp难多了 自己感觉...

而且 这题的来源是 我上次去的 牡丹江区域赛..

FML------不想多说了

dp[ i ][ j ][ k ]表示用 k 个棋子占领了 I 行 J 列 < 每一个坐标为(x,y)的棋子都可以占领它所在的第 X 行 第 Y 列 >

那么假如现在已经放了K个棋子 并且占领了 I 行 J列 那么对于将要放下去的第(k+1)个棋子 将会有4种不同情况的发生<保证棋盘还有空格在还可以继续放的情况下>

这里的 n * m - k 就是指一共有n * m 个格子已经放了k个格子 还可以放的格子数量

1.-这第(k+1)个棋子放在了已经占领的 I 行 J列 中的某行某列中

可以求出 P1 = ( i * j  - k ) / ( n * m - k )

对应 状态转移方程 则是 dp[ i ] [ j ] [ k ] = dp[ i ] [ j ] [ k-1 ] * P1 ;

2.-这第(k+1)个棋子放在 已占领的某J列之一中但不在已占领的某I行 之一

可以求出P2 = ( n - i ) * j / ( n * m - k )

对应 dp[ i+1 ][ j ][ k ] = dp[ i ][ j ][ k-1 ] * P2;//这个棋子又多占领了 一行

3-这第(k+1)个棋子放在 已占领的某I行之一中但不在已占领的某J列 之一

可以求出P3 = ( m-j ) * i / ( n * m - k )

对应 dp[ i ][ j+1 ][ k ] = dp[ i ][ j ]][ k-1 ] * P3;//这个棋子又多占领了一列

4-这第(k+1)个棋子放在 未占领(n-i)行与(m-j)列之上

可以求出P4 = ( n - i ) * ( m - j ) / ( n * m - k )

对应 dp[ i+1 ][ j+1 ][ k ] = dp[ i ][ j ][ k-1 ] * P4;//这个棋子又多占领了 一行 和 一列

其实 我们可以发现在 n >=1 && m>=1 的情况下 最少需要放置的棋子数量是1  最多需要放置的棋子数量是 maxNum = ( max(n,m)-1 ) * min(n,m) + 1

最好就是一个累加求和了

ans = Sigma( dp[n][m][k] ) k = 1,2,………maxNum;

 1 #include <iostream> 2 #include <cstring> 3 #include <iomanip> 4 #include <algorithm> 5 using namespace std; 6  7 const int size = 55; 8 double dp[size][size][size*size]; 9 10 int main()11 {12     int t , n ,m , maxNum;13     double ans;14     cin >> t;15     while( t-- )16     {17         ans = 0;18         memset( dp , 0 , sizeof(dp) );19         dp[0][0][0] = 1;20         cin >> n >> m;21         maxNum = ( max(n,m)-1 ) * min(n,m) + 1;22         for( int i = 1 ; i<=n ; i++ )23         {24             for( int j = 1 ; j<=m ; j++ )25             {26                 for( int k = 1 ; k<=maxNum ; k++ )27                 {28                     dp[i][j][k] = ( dp[i-1][j][k-1] * (n-i+1) * j  + dp[i][j-1][k-1] * (m-j+1) * i  + dp[i-1][j-1][k-1] * (n-i+1) * (m-j+1) ) / ( n*m-k+1 );29                     if( i==n && j==m )30                         continue;31                     else32                         dp[i][j][k] += dp[i][j][k-1] * ( i*j-k+1 ) / (n*m-k+1);33                 }34             }35         }36         for( int k = 1 ; k<=maxNum ; k++ )37         {38             ans += k * dp[n][m][k];39         }40         cout << setiosflags(ios::fixed);41         cout << setprecision(12) << ans <<endl;42     }43     return 0;44 }
View Code

 

today:

  为什么我们期待的事总是不会到来呢?

  因为我们人为地给它增加了发生概率 甚至逼近100%

  但是我们害怕的事总是会到来

  因为我们自己的恐惧而导致我们自己不能发挥平常的水准

 

zoj--3822--第二题概率dp