POJ 1322 초콜릿 (확률 DP)

Description c 가지 색상 의 초콜릿 은 각각 무한 개가 있 습 니 다. 지금 은 확률 적 으로 n 개의 초콜릿 을 꺼 내 책상 위 에 놓 아야 합 니 다. 만약 에 책상 위 에 두 개의 초콜릿 색깔 이 있 으 면 똑 같이 먹 습 니 다. 마지막 책상 에 m 개의 초콜릿 이 남 을 확률 을 물 어보 세 요. Input 여러 조 의 사례 는 3 개의 정수 c, n (c < 100, n, m < = 1000000) 이 고 0 으로 출력 을 입력 하 는 것 이 각 조 의 사례 입 니 다.출력 에서 초콜릿 n 조각 을 꺼 낸 후 테이블 에 초콜릿 m 조각 이 남 을 확률 Sample Input 5 1002 0 Sample Output 0.625 Solution 확률 문 제 는 dp [i] [j] 로 초콜릿 i 조각 을 가 져 온 후 j 조각 이 남 을 확률 을 나타 내 면 전이 방정식 dp [i] [j] = dp [i - 1] [j - 1] * (c - j + 1) / c + dp [i - 1] [j + 1] * (j + 1) / c 를 쉽게 쓸 수 있다. 방정식 을 보면 알 수 있다.첫 번 째 는 스크롤 배열 로 공간 을 절약 할 수 있 지만 이렇게 하 는 시간 복잡 도 는 O (10 ^ 8) 이기 때문에 최적화 해 야 한다. 분석 을 통 해 알 수 있 듯 이 i + j 가 홀수 일 때 dp [i] [j] = 0 이다. 이것 은 매번 같은 색깔 의 초콜릿 두 개 를 먹 기 때문에 i - j 는 반드시 짝수 이다. 이렇게 하면 절반 의 복잡 도 를 낮 출 수 있 지만 시간 을 초과 할 수 있 기 때문에 수출 에 있어 서 최적화 된다.3 자리 소수 만 유지 해 야 하기 때문에 n > 1000 일 때 는 1000 위 권 이나 1001 (n 의 패 리 티 에 따라) 개의 초콜릿 만 고려 해 야 합 니 다. 그 다음 에 초콜릿 을 꺼 내 서 결과 에 대한 기여 가 너무 작 으 면 수출 에서 무시 되 기 때문에 고려 하지 않 아 도 됩 니 다. 그러면 시간 복잡 도 는 O (5 * 10 ^ 4) Code 입 니 다.
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 111
double dp[2][maxn];
int c,n,m;
int main()
{
    while(scanf("%d%d%d",&c,&n,&m),c)
    {
        memset(dp,0,sizeof(dp));
        if(m>n||m>c||(m+n)%2)
        {
            printf("0.000
");
            continue;
        }
        if(n>1000)n=1000+n%2;
        dp[0][0]=1.0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=i&&j<=c;j++)
            {
                dp[i%2][j]=0;
                if((i+j)%2)continue;
                if(j>0)dp[i%2][j]+=dp[1-i%2][j-1]*(c-j+1)/c;
                if(j+1<=i-1)dp[i%2][j]+=dp[1-i%2][j+1]*(j+1)/c;
            }
        printf("%.3lf
",dp[n%2][m]);
    }
    return 0;
}
androidlistview 시리즈의 item 클릭 이벤트 및 item 레이아웃의 클릭 이벤트 (4)
셸 스 크 립 트 명령 -- cut (문자 캡 처), sort (문자 정렬)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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