CFR 518 D. Ilya and Escalator ( Expectation DP )

Problem - D - Codeforces
題意：
N 個人排成一排，每秒隊首有 P 的機率進電梯，1 - P 的機率停留原地。求 T 秒後，期望有多少人在電梯裡。
解法：
dp[ i ][ j ] : 已經過 i 秒，電梯裡有 j 個人的機率。
dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] * P + dp[ i - 1 ][ j ] * ( 1 - P )

int N, T;
double P;

void init(){
    cin >> N >> P >> T;
}

vvd dp;

void preprocess(){
    dp = vvd( T + 1, vd( N + 1 ) );
    dp[ 0 ][ 0 ] = 1.0;
    for( int i = 0; i < T; ++i )
        for( int j = 0; j <= N; ++j ){
            if( j == N )
                dp[ i + 1 ][ j ] += dp[ i ][ j ];
            else
                dp[ i + 1 ][ j ] += dp[ i ][ j ] * ( 1.0 - P ),
                dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ] * P;
        }
}

void solve(){
    double ans = 0.0;
    for( int i = 1; i <= N; ++i )
        ans += dp[ T ][ i ] * i;
    cout << fixed << setprecision( 9 ) << ans << endl;
}