poj 1322 Chocolate (概率dp)

///有c种不同颜色的巧克力，一个个的取，当发现有相同的颜色的就吃掉，去了n个后，到最后还剩m个的概率
///dp[i][j]表示取了i个还剩j个的概率
///当m+n为奇时，概率为0
# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <iostream>
using namespace std;
double dp[1010][1010];
int main()
{

   int i,j,n,m,c;
    while(~scanf("%d",&c),c)
    {
        scanf("%d%d",&n,&m);
        if(m>c||m>n||(n+m)%2)
            printf("0.000\n");
        else
        {
            if(n>1000)
              n=1000+n%2;
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(i=1;i<=n;i++)
            {

                dp[i][0]=dp[i-1][1]/c;
                dp[i][c]=dp[i-1][c-1]/c;
                for(j=1;j<c;j++)
                dp[i][j]=dp[i-1][j-1]*(c-j+1)/(c*1.0)+dp[i-1][j+1]*(j+1)/(c*1.0);
            }
            printf("%.3lf\n",dp[n][m]);
        }

    }
    return 0;
}

poj 1322 Chocolate (概率dp)

原文：http://blog.csdn.net/lp_opai/article/details/39781983