首页 > 代码库 > 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 }
today:
为什么我们期待的事总是不会到来呢？
因为我们人为地给它增加了发生概率 甚至逼近100%
但是我们害怕的事总是会到来
因为我们自己的恐惧而导致我们自己不能发挥平常的水准
zoj--3822--第二题概率dp