ZOJ 3582 Back to the Past

dp[i][j]记录从当前状态到结束状态的期望。。。

dp[i][j]=1+segma( dp[i+a][j+b]*P(a,b) )   a  0..n-i   b  0..n-j

递归就可以了，a==0&&b==0的时候要特判一下

Recently poet Mr. po encountered a serious problem, rumor said some of his early poems are written by others. This brought a lot of trouble to Mr. po, so one day he went to his best friend MasterO for help. MasterO handed over a small wooden box with a silent smile. Mr. po checked the box, a word "YGBH" carved on the side. "The box can take you back to the past," MasterO said, "so you can get any evidence you need. But, before that, you need some patience."

There are N tiny dark holes on both sides of the box (2N holes in total). Every day, for each hole, there is a possibility P to successfully absorb the power of moon and then magically sparkle. The possibilities among holes are independent in each day. Once a hole sparkles, it will never turn dark again. The box only works when there are no less than M sparkling holes on each side of the box. The question is that what is the expected number of days before the box is available.

Input

The input consists of several test cases. For each case there are 3 numbers in a line: N, M, P. 1 ≤ N ≤ 50, 1 ≤ M ≤ N, 0.01 ≤ P ≤ 1. A case with three zeros indicates the end of the input.

Output

For each test case, output the expected number of days, accurate up to six decimal places.

Sample Input

2 1 1
1 1 0.5
0 0 0

Sample Output

1.000000
2.666667

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps=1e-9;

int N,M;
long long CM[100][100];
double P,pp[100],app[100],dp[100][100];

void initCOMP()
{
    for(int i=0;i<=51;i++)
        CM[i][0]=CM[i][i]=1;
    for(int i=2;i<=51;i++)
    {
        for(int j=1;j<i;j++)
            CM[i][j]=CM[i-1][j]+CM[i-1][j-1];
    }
}

void init()
{
    memset(pp,0,sizeof(pp));
    memset(app,0,sizeof(app));

    app[0]=pp[0]=1.;

    for(int i=1;i<=50;i++)
    {
        app[i]=app[i-1]*(1-P);
        pp[i]=pp[i-1]*P;
    }

    memset(dp,0,sizeof(dp));
}

double getPP(int i,int j,int a,int b)
{
    return CM[N-i][a]*pp[a]*app[N-i-a]*CM[N-j][b]*pp[b]*app[N-j-b];
}

double dfs(int left,int right)
{
    if(left>=M&&right>=M) return 0;
    if(fabs(dp[left][right])>eps) return dp[left][right];

    dp[left][right]=1.;
    for(int a=0;a<=N-left;a++)
    {
        for(int b=0;b<=N-right;b++)
        {
            if(a==0&&b==0) continue;
            dp[left][right]+= getPP(left,right,a,b) * dfs(left+a,right+b);
        }
    }

    return dp[left][right]/=1-getPP(left,right,0,0);
}

int main()
{
    initCOMP();
while(cin>>N>>M>>P&&N&&M)
{
    init();
    printf("%.6lf\n",dfs(0,0));
}
    return 0;
}

ZOJ 3582 Back to the Past

原文：http://blog.csdn.net/u012797220/article/details/19717853