首页 > 代码库 > zoj 2949 - Coins of Luck

zoj 2949 - Coins of Luck

题目:有2中面条各n碗。每次抛硬币推断吃哪一种(到一种吃完为止)。问抛硬币的数学期望。

分析:动态规划。概率dp。求出每种结束状态(即,有一种吃完)的概率,分别乘以步长即为期望。

             大黄解法:状态位剩余的碗数,逆向求解,状态方程:

                DP[ i ][ j ] = (DP[ i-1 ][ j ]+DP[ i ][ j-1 ])/2 + 1 { orz~~ (所有20行代码就能搞定) }。

说明:(2011-09-27 03:22)。

#include <stdio.h>
#include <stdlib.h>

double p[ 1002 ][ 1002 ];
double q[ 1002 ];

int main()
{
    for ( int i = 0 ; i <= 1000 ; ++ i )
    for ( int j = 0 ; j <= 1000 ; ++ j )
        p[ i ][ j ] = 0.0;
    p[ 0 ][ 0 ] = 1.0;
    for ( int i = 0 ; i <= 1000 ; ++ i )
    for ( int j = 0 ; j <= 1000 ; ++ j ) {
        p[ i+1 ][ j ] += p[ i ][ j ]*0.5;
        p[ i ][ j+1 ] += p[ i ][ j ]*0.5;
    }
    
    for ( int i = 1 ; i <= 1000 ; ++ i ) {
        double sum = p[ i ][ 0 ]*i;
        for ( int j = i-1 ; j >= 1 ; -- j ) 
            sum += (i+j)*(p[ i ][ j ]-p[ i ][ j-1 ]*0.5);
        q[ i ] = sum*2.0;
    }
    
    int t,n;
    while ( scanf("%d",&t) != EOF ) 
    while ( t -- ) {
        scanf("%d",&n);
        printf("%.2lf\n",q[ n ]);
    }
    return 0;
}

zoj 2949 - Coins of Luck