题目：有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;

}