poj-1322-Chocolate 는 동적 계획 을 사용 하여 해답 을 구 하 는 확률 적 인 문제 의 알고리즘

원 제 는 다음 과 같다.
Chocolate
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 7931
 
Accepted: 2078
 
Special Judge
Description
In 2100, ACM chocolate will be one of the favorite foods in the world. 
"Green, orange, brown, red...", colorful sugar-coated shell maybe is the most attractive feature of ACM chocolate. How many colors have you ever seen? Nowadays, it's said that the ACM chooses from a palette of twenty-four colors to paint their delicious candy bits. 
One day, Sandy played a game on a big package of ACM chocolates which contains five colors (green, orange, brown, red and yellow). Each time he took one chocolate from the package and placed it on the table. If there were two chocolates of the same color on the table, he ate both of them. He found a quite interesting thing that in most of the time there were always 2 or 3 chocolates on the table. 
Now, here comes the problem, if there are C colors of ACM chocolates in the package (colors are distributed evenly), after N chocolates are taken from the package, what's the probability that there is exactly M chocolates on the table? Would you please write a program to figure it out? 
Input
The input file for this problem contains several test cases, one per line. 
For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000). 
The input is terminated by a line containing a single zero. 
Output
The output should be one real number per line, shows the probability for each case, round to three decimal places.
Sample Input

5 100 2

0

Sample Output

0.625 

제목 의 대 의 는 기 존의 c 가지 색깔 의 초콜릿 을 상자 에 넣 고 그 중에서 하 나 를 꺼 내 책상 위 에 놓 을 수 있다 는 것 이다.매번 에 각 색깔 의 초콜릿 을 꺼 낼 확률 이 같다(즉 1/c)는 것 이다.만약 에 방금 꺼 낸 이 색깔 이 책상 위 에 있 는 어떤 초콜릿 의 색깔 과 같다 면 이 두 개 를 모두 먹 어 라.해 를 요구 하 는 것 은 n 번 을 뽑 은 후에 책상 위 에 초콜릿 m 개가 남 을 확률 이 얼마 입 니까?
이 문제 의 사고방식 은 아래 와 같다.
첫 번 째 로 꺼 냈 을 때 책상 위 에 다른 사탕 이 없 었 기 때문에 이때 책상 위 에 1 개 만 남 았 을 가능성 이 있 고 확률 은 1 이다.
두 번 째 로 꺼 낼 때 책상 위 에 이미 하나 가 있 기 때문에 두 가지 상황 이 있 습 니 다.
(1)이번에 꺼 낸 것 은 기 존의 그 색깔 과 똑 같이 모두 먹고 0 개 남 았 다.이런 상황 이 발생 할 확률 은 1/c 이다.
(2)이번에 꺼 낸 것 은 기 존의 그 색깔 과 달리 모두 책상 위 에 남 고 두 개 남 았 다.이러한 상황 이 발생 할 확률 은(c-1)/c 이다.
세 번 째 로 꺼 낼 때 책상 위의 상황 은 두 가지 가능성 이 있다.
(1)이때 책상 위 에 0 개가 있 으 면 이번에 꺼 낸 것 은 반드시 책상 위 에 남 을 수 있다.즉,책상 위 에 1 개 를 남 길 수 있다.이러한 상황 이 발생 할 확률 은 조건 확률,즉(1/c)*1=1/c 이다.
(2)이때 책상 위 에 두 개가 있 으 면 이번에 꺼 낸 것 은 두 가지 가능성 이 있다.
1)、이번에 꺼 낸 것 은 기 존의 두 개 중 한 개 색깔 과 같 으 면 책상 위 에 1 개 만 남 습 니 다.확률 은[(c-1)/c]*(2/c)입 니 다.
2)이번에 꺼 낸 것 은 기 존의 두 가지 색깔 과 다 르 기 때문에 3 개 를 모두 책상 위 에 남 길 수 있 습 니 다.확률 은[(c-1)/c]*[(c-2)/c]입 니 다.
。。。。。。
상기 소 규모 데이터 상황 에 대한 분석 을 통 해 사탕 을 꺼 낼 때마다 책상 위의 상황 은 지난번 에 꺼 낼 때 발생 할 수 있 는 상황 을 통 해 추산 할 수 있다.필요 한 상 태 는 매개 변수 가 현재 의 횟수(i 로 설정)와 책상 위 에 남 은 사탕 수량(j 로 설정)임 을 나타 낸다.
그렇다면 5 가지 색상 으로 예 를 들 어 다음 표 로 여러 상태 에서 저장 할 확률 은 다음 과 같다.
 횟수\남 음
        0       
       1       
       2       
       3       
  。。。 
0
1
0
0
0
。。。
1
0
1
0
0
。。。
2
1/5
0
4/5
0
。。。
3
0
13/25
0
12/25
。。。
。。。
。。。
。。。
。。。
。。。
。。。
(녹색 으로 표 시 된 데 이 터 를 틀 리 지 않도록 주의 하 세 요.
위의 표 에서 발견 할 수 있 습 니 다:
1.i 와 j 의 패 리 티 가 다 르 면 확률 은 0 이다.이것 은 매번 먹 히 는 것 이 2 개 또는 0 개 밖 에 안 되 기 때문이다.
2.j>i 일 때 확률 은 모두 0 이다.i 번 만 가 질 수 없 지만 i 보다 더 많은 사탕 을 남 길 수 없 기 때문이다.
3.이 표를 계산 할 때 상태(i,j)에 대해 그 확률 은(i-1,j-1)과(i-1,j+1)로 계산 할 수 있다.이것 은 이번에 j 개 를 남 긴 이상 지난번 에 남 은 것 은 j-1 개 또는 j+1 개(제1 조 와 결합 하여 이해)일 수 있 기 때문이다.
     예 를 들 어 상태(3,1),P(3,1)=P(2,0)*[5-(1-1)]/5+P(2,2)*(2/5)=13/25
     상기 홍 보 를 통 해 본 문제 의 상태 이전 식 을 얻 을 수 있 습 니 다.P(i,j)=P(i-1,j-1)*[(c-(j-1)]/c+P(i-1,j+1)*[(j+1)/c]
이상 의 결론 을 얻 은 후에 본 문제 의 해결 절 차 를 쓸 수 있 지만 주의해 야 할 것 이 하나 있다.본 문제 의 요구 결 과 는 3 자리 소수 만 유지 해 야 하기 때문에 i 가 매우 클 때 그 확률 변화 가 미미 하고 필요 한 자릿수 에 영향 을 주지 않 기 때문에 순환 횟수 를 줄 여 시간 을 절약 할 수 있 지만 방금 말 한 제1조,즉 기이 성 은 반드시 유지 해 야 한 다 는 것 을 주의해 야 한다.
코드 는 다음 과 같 습 니 다:

#include
#include
double dp[1005][105];
int main()
{
	int c,n,m;
	while(scanf("%d",&c)&&c)
	{
		scanf("%d%d",&n,&m);
		if(m>n||m>c||(m%2==0&&n%2!=0)||(m%2!=0&&n%2==0))
		{
			printf("0.000
");
			continue;
		}
		if(n>1000)
		{
			if(n%2==0)	n=1000;
			else		n=1001;
		}
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=n;++i)
		{
			dp[i][0]=dp[i-1][1]/c;
			dp[i][c]=dp[i-1][c-1]/c;
			for(int j=1;j