codeforces 518D D. Ilya and Escalator(확률 dp)

제목 링크:


codeforces 518D

제목 대의:


n명, 초당 p의 확률로 한 사람이 엘리베이터에 들어간다. t초 후 엘리베이터 안의 인원수에 대한 기대를 물어본다.

제목 분석:


4
  • 정의 dp[i][j]는 i초 엘리베이터에 j 개인이 있을 확률을 나타낸다
  • j!=n시,
    dp[i][j]=p⋅dp[i−1][j−1]+(1−p)⋅dp[i−1][j]

  • 4
  • j=n시,
    dp[i][j]=p⋅dp[i−1][j−1]+dp[i−1][j]

  • 4
  • 만약에 n 개인이 다 사용하면 뒤의 상태는 100% 현재 상태의 모든 확률을 계승할 수 있기 때문이다.

  • AC 코드:

    #include 
    #include 
    #include 
    #include 
    #define MAX 2007
    
    using namespace std;
    
    double dp[MAX][MAX],p;
    int n,t;
    
    
    int main ( )
    {
        while ( ~scanf ( "%d%lf%d" , &n , &p , &t ) )
        {
            memset ( dp , 0 , sizeof ( dp ));
            dp[0][0] = 1;
            for ( int i = 1 ; i <= t ; i++ )
                for ( int j = 0 ; j <= n ; j++ )
                {
                    if ( j == n )dp[i][j] = dp[i-1][j];
                    else dp[i][j] = (1-p)*dp[i-1][j];
                    if ( j )
                        dp[i][j] += p*dp[i-1][j-1];
                    //sum[i][j] += sum[i-1][j] + dp[i][j];
                }
            double ans = 0;
            for ( int i = 1 ; i <= n ; i++ )
                ans += dp[t][i]*i;
            printf ( "%.7f
    "
    , ans ); } }

    좋은 웹페이지 즐겨찾기