gdfzoj \ # 470 Red is good (수학 적 기대)

머리말
처음으로 블 로 그 를...원본 링크:http://www.gdfzoj.com/oj/problem/470 수학 적 기대
제목 설명
Problem 470: [HbFS-]Red is good Time Limit: 1000 ms Memory Limit: 524288 KB
Problem Description 데스크 톱 에는 R 장의 레드카드 와 B 장의 블랙 카드 가 있 습 니 다. 무 작위 로 순 서 를 흐 트 러 뜨 린 후 데스크 톱 에 놓 고 한 장 한 장 씩 카드 를 뒤 집 기 시작 합 니 다. 레드 카드 를 뒤 집 으 면 1 달러 를 받 고 블랙 카드 는 1 달러 를 받 습 니 다.언제든지 카드 뒤 집기 를 멈 출 수 있 고, 가장 좋 은 전략 에서 평균 얼 마 를 받 을 수 있다.답 을 출력 할 때 소수점 후 6 위 후의 것 은 모두 제거 하고 반올림 하지 마 세 요.
Input 한 줄 에 두 개의 숫자 R, B 를 입력 하면 그 값 은 0 에서 5000 사이 입 니 다.
Output 은 최 적 화 된 전략 에서 평균 얼 마 를 얻 을 수 있 습 니까?
Sample Input 5 1
Sample Output 4.166666
분석 하 다.
주제 의 뜻 을 직접 보면 생각 이 없 는 것 같 지만 적당 한 전략 을 생각 할 수 있다 면 해법 이 비교적 뚜렷 하 다.먼저 해법 전략 을 고려 할 때 우 리 는 '좋 은 것 을 보면 받 을 수 있다' 는 전략 을 사용 할 수 있다. 바로 다음 카드 를 떼 고 남 은 레드카드 의 수량 이 남 은 블랙 카드 의 수량 보다 많 으 면 수학 기대 공식 을 운반 하 는 것 이다.
E(x)=∑i=1nXiPi
이 공식 이 있 으 면 우 리 는 E (x, y) 를 설정 하여 남 은 x 장의 레드카드 를 받 을 때 y 장의 블랙 카드 는 기대 치 를 나 타 낼 수 있다.
그렇다면 전달 공식 은
E(x,y)=xx+y(E(x−1,y)+1)+yx+y(E(x,y−1)−1)
그 중에서 도 앞 에 서 는 레드카드 를 받 은 경우, 뒤 에는 레드카드 를 받 은 경 우 를 나타 낸다.
그리고 특 판 을 진행 해 E (x, y) 가 0 보다 적 으 면 나머지 레드카드 의 수가 남 은 블랙 카드 의 수 보다 적 다 는 뜻 이 라면 뒤 집기 가 중단 된다.
마지막 으로 E (R, B) 를 출력 하 는 것 이 답 이다.
코드

#include
#define max 5500
using namespace std;
int i,j,r,b;
double e[max][max],ll,rr;
int main()
{
    scanf("%d%d",&r,&b); 
    //for (i=0;i<=r;i++) e[i][0]=i;
    for (i=0;i<=r;i++)
        for (j=0;j<=b;j++)
        {
            ll=(double)i/(double)(i+j); rr=(double)j/(double)(i+j);
            if (i) e[i][j]+=(e[i-1][j]+1)*ll;
            if (j) e[i][j]+=(e[i][j-1]-1)*rr;
            if (e[i][j]<0) e[i][j]=0;
        }
    printf("%.6f",e[r][b]-0.0000005);
    return 0;    
}