TopCoder SRM 626 div1 250( 条件概率 )

就会这一道，还是赛后十几分钟才做出...

题意 : Alice 要投a个b面体筛子，Bob投c个d面体筛子。已知结果是Alice赢了，问Alice期望的分数是多少?

思路 : 如何计算Alice分数的期望 ， 我们需要利用分布律来计算 ， 即 E = P[i] * i 其中 i 是在Alice获胜的情况下，Alice得分为i的概率

           那么如何计算 P[i] , 那么我们就需要通过条件概率的公式去计算了

           P[i] = P( A | B ) = P( AB ) / P( B )

           A 事件为 Alice 投出的分数为 i ，B事件为Alice获胜

那么为了计算P(AB)和P(B)，那么，我们就需要计算出Alice和Bob分别投出分数 i 的概率 ， 假设 Pa[i] 为Alice投出分数 i 的概率， Pb[i]为Bob投出分数i的概率

计算Pa[i] : 设 f[i][j] 表示为前i个筛子，投出总和为j的方案数，然后每个方案数除以总和即可 。

那么 P( AB ) = Pa[i] * Σ( Pb[j] ) , j < i

         P( B ) = Σ ( Pa[i] * Pb[j] ) , j < i

下面是代码 : 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

class FixedDiceGameDiv1 {
public:
	double f[55][2555] ;
	double pa[2555] , pb[2555] ;
	double sb[2555] ;

	double getExpectation(int a, int b, int c, int d){
		double ans = 0 ;
		if( a * b <= c )
			return -1.0 ;
		memset( pa , 0 , sizeof(pa) );
		memset( pb , 0 , sizeof(pb) );
		memset( f , 0 , sizeof(f) ) ;

		f[0][0] = 1 ;
		for( int i = 1 ; i <= a ; i ++ ) {
			for( int j = 1 ; j <= a * b ;j ++ ) {
				for( int k = 1 ; k <= b ; k ++ ) {
					if( k <= j )
						f[i][j] += f[i-1][j-k] ;
				}
			}
		}

		double sum = 0 ;
		for( int i = a ; i <= a * b ; i ++ ) {
			pa[i] = f[a][i] ;
			sum += f[a][i] ;
		}
		for( int i = 1 ; i <= a * b ; i ++ ) {
			pa[i] /= sum ;
		}
		memset( f , 0 , sizeof(f) ) ;
		f[0][0] = 1 ;
		for( int i = 1 ; i <= c ; i ++ ) {
			for( int j = 1 ; j <= c * d ;j ++ ) {
				for( int k = 1 ; k <= d ; k ++ ) {
					if( k <= j )
						f[i][j] += f[i-1][j-k] ;
				}
			}
		}
		sum = 0 ;
		for( int i = c ; i <= c * d ; i ++ ) {
			pb[i] = f[c][i] ;
			sum += f[c][i] ;
		}
		for( int i = c ; i <= c * d ; i ++ ) {
			pb[i] /= sum ;
		}
		sum = 0 ;
		for( int i = a ; i <= a * b ; i ++ ) {
			for( int j = c ; j < i ; j ++ ) {
				sum += ( pa[i] * pb[j] ) ;
			}
		}
		memset( sb , 0 , sizeof(sb) ) ;
		for( int i = c ; i <= a * b ; i ++ ) {
			sb[i] = pb[i] + sb[i-1] ;
		}	
		ans = 0 ;
		for( int i = a ; i <= a * b ; i ++ )
			ans += pa[i] * sb[i-1] / sum * i ;
		return ans ;
	}	
};