POJ1322 Chocolate dp

剛開始做這得時，dp方程很容易寫出來。。。

dp(n+1,m+1)+=dp(n,m)*(c-m)/c

dp(n+1,m-1)+=dp(n,m)*m/c;

可根據這個思想寫時，剛開始記憶體不夠，改正之後一直逾時（第一次另開個數組存結果，後來直接判斷奇偶性，這都逾時了）。。

實在沒招，看了别人的，才知道這題用了個小技巧。。題目隻要求保留三位有效數字，即對精度要求不是很高。根據統計學結果，當n足夠大時，所求機率應趨于一個常數，即題目所求值。

#include<stdio.h>
#include<string.h>
double d[101][2];
int c,n,m;
int main()
{
	while(~scanf("%d",&c)&&c)
	{
		scanf("%d%d",&n,&m);
		if(m>c||m>n||(m+n)%2)
		{
			printf("0.000\n");
			continue;
		}		
		int i,k,j;
		if(n > 1000)  
            n = n % 2 ? 1001 : 1000; 
		memset(d,0,sizeof(d[0])*(c+1));
		d[0][0]=1.0;
		for(i=1;i<=n;i++)
		{
			int x=i%2,y=(i+1)%2;
			d[1][x]+=d[0][y];
			d[0][y]=0;
			for(j=1;j<=c-1;j++)
			{	
				d[j-1][x]+=d[j][y]*j/c*1.0;
				d[j+1][x]+=d[j][y]*(c-j)/c*1.0;
				d[j][y]=0;
			}
			d[c-1][x]+=d[c][y];
			d[c][y]=0;			
		}
		printf("%.3f\n",d[m][(n)%2]);
	}
	return 0;
}