codeforces 148D D. Bag of mice(확률 dp)

4950 단어 dpcodeforces확률 DP

제목 링크:


codeforces 148D

제목 대의:


w마리의 흰 쥐, b마리의 검은 쥐를 주고 공주와 용이 번갈아 쥐를 잡는다. 공주가 먼저 쥐를 잡는다. 용이 쥐를 잡을 때 한 마리의 쥐를 놀라 도망가게 한다. 먼저 흰 쥐를 뽑는 사람이 이긴다. 만약에 흰 쥐를 뽑는 사람이 없다면 용이 이긴다.공주가 이길 확률을 묻는다.

제목 분석:

  • 우선 상태 dp[i][j]를 정의하고 i번에 쥐를 잡았을 때 남은 검은 쥐가 j일 확률을 나타낸다.
  • 그럼 마지막 결과는
    ∑i는 홀수 ∑j=0bdp[i][j]
  • 그럼 어떻게 옮겨요?두 가지 상황으로 나누다
  • i&1 :
    dp[i][j]=dp[i−1][j+1]⋅j+1sumi−1
  • else:
    dp[i][j]=dp[i−1][j+1]⋅(j+1)⋅(sumi−1−j−1)sumi−1⋅sumi−1−1

  • 그 다음에 경계 상황을 주의해야 한다. 더블 값이 경계 상황에 있어 많은 상황이 나타날 수 있기 때문에 구체적인 특판 코드

    • AC 코드:

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 1007

using namespace std;

double dp[MAX][MAX];
int w,b,sum;

void calc ( int x )
{
    sum = x+x/2;
    sum = w+b-sum;
}

int main ( )
{
    while ( ~scanf ( "%d%d" , &w , &b ) )
    {
        if ( w == 0 )
        {
            puts ("0.0000000000" );
            continue;
        }
        memset ( dp , 0 ,sizeof ( dp ) );
        dp[0][b] = 1.0;
        for ( int i = 1 ; i <= b; i++ )
        {
            calc ( i-1 );
            for ( int j = 0; j <= b ; j++ )
            {
                dp[i][j] = 0;
                if ( i&1 )
                    dp[i][j] = dp[i-1][j+1]*((j+1)*1.0/(sum*1.0));
                else 
                {
                    double x = (j+1)*(j+2)*1.0/(sum*(sum-1)*1.0);
                    dp[i][j] += dp[i-1][j+2]*x;
                    x = (j+1)*(sum-1-j)*1.0/(sum*(sum-1)*1.0);
                    dp[i][j] += dp[i-1][j+1]*x;
                }
            }
        }
        double ans = 0;
        for ( int i = 0 ; i <= b ; i += 2 )
            for ( int j = 0 ; j <= b ; j++ )
            {
                calc ( i );
                if ( sum == 0 || sum < j  ) continue;
                //cout << dp[i][j] << " " << ans << endl;
                ans += dp[i][j]*((sum-j) *1.0/(sum*1.0));
            }
        printf ( "%.10lf
    "     , ans );
    }
}
    초보자를 위한 JavaScript 5가지 유형
    그레이스 만져봐.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage