学步园

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

using namespace std;

const int maxn=2000+3;
const double eps=10e-9;
double p[5];
double dp[maxn][maxn];
double ps[maxn];
double c[maxn];

int main ()
{
    int n, m, k;
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        memset (dp, 0, sizeof(dp));
        for (int i=1; i<=4; ++i)
            scanf("%lf", p+i);
        if (fabs(p[3]+p[4])<eps)
        {
            puts("0.00000");
            continue;
        }
        dp[1][1]=p[4]/(p[3]+p[4]);
        p[2]=p[2]/(1-p[1]);
        p[3]=p[3]/(1-p[1]);
        p[4]=p[4]/(1-p[1]);

        ///dp[i][1]=p2*(p2*(p2(... (p2*d[i][1]+c[1])...)+c[i-2])+c[i-1])+p4
        ///        =p2^i*dp[i][1]+p2^(i-1)*c[1]+...p2*c[i-1]+c[i];
        ps[0]=1.0;
        for (int i=0; i<=n; ++i)
            ps[i+1]=ps[i]*p[2];
        c[1]=p[4];
        //printf("%lf  %lf\n", ps[1], ps[2]);
        for (int i=2; i<=n; ++i)
        {
            for (int j=2; j<=k; ++j)
                c[j]=p[3]*dp[i-1][j-1]+p[4];
            for (int j=k+1; j<=i; ++j)
                c[j]=p[3]*dp[i-1][j-1];

            dp[i][1]=p[4];
            for (int j=1; j<i; ++j)
                dp[i][1]+=ps[i-j]*c[j+1];
            dp[i][1]/=(1-ps[i]);

            for (int j=2; j<=i; ++j)
                dp[i][j]=p[2]*dp[i][j-1]+c[j];
//            for (int j=k+1; j<=i; ++j)
//                dp[i][j]=p2*dp[i][j-1]+c[j-1];
        }

//        for (int i=1; i<=n; ++i)
//        {
//            for (int j=1; j<=i; ++j)
//                printf("%lf ", dp[i][j]);
//            printf("\n");
//        }
        printf("%0.5lf\n", dp[n][m]);
    }
    return 0;
}