/*
    这道题是请教了watashi神牛才懂的，真的是神牛做题如切菜~~~
    题意：一篇文章n个字符，每打一个字符（包括空格）需要1个单位时间。时不时可以用t个时间去检查错误
          发现错误，用空格退到第一个错误的地方，然后重新打
          给出每个字符错误的概率，问打完这篇文章所需最小时间的期望

    最小时间，肯定有一个选择的过程，用DP解决。还有，期望题一般设的是当前状态离结束的代价

    设dp[i]表示i之前的单词已经正确打完了，从i开始到结束还需要的时间
    初始dp[n+1]=0 答案就是dp[0]了
    枚举从i开始打完k个字符后就检查
    dp[i]=min{
            (t+k)
            +q[i]*(dp[i]+k)
            +p[i]*q[i+1]*(dp[i+1]+k-1)
            +
            +p[i]**p[i+k-2]*q[i+k-1]*(dp[i+k-1]+1)
            +p[i]**p[i+k-2]*p[i+k-1]*dp[i+k]
        }
    p[i]是正确的概率，q[i]是错误的概率
    意思是：一口气打了k个，然后用t时间检查。检查的结果就是哪个是第一个错误的（p[i]*p[j-1]*q[j]）
    O(n^2)    
*/

#include<cstdio>

const int MAXN = 3001;
const double DINF = 1e100;

double q[MAXN],dp[MAXN];

int main()
{
    for(int t,n;~scanf("%d%d",&n,&t);)
    {
        for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
        dp[n+1]=0;
        for(int i=n;i;i--)
        {            
            double sum = t+1+q[i]+(1-q[i])*dp[i+1];
            double inc = 1+q[i];//记录与k有关的
            double p = 1-q[i];
            dp[i]=sum;
            for(int k=2;i+k<=n+1;k++)
            {
                sum=sum-p*dp[i+k-1]+p*q[i+k-1]*(dp[i+k-1]+1)+p*(1-q[i+k-1])*dp[i+k]+inc;
                inc+=p*q[i+k-1];
                p*=(1-q[i+k-1]);
                if(sum<dp[i])dp[i]=sum;
            }
            dp[i]/=(1-q[i]);
        }
        printf("%.8f\n",dp[1]);
    }
    return 0;
}

SCAU 2010 校赛A题 Fast Typing  跟上面类似，多了一点计算而已
/*
    跟sgu 422 类似 多了一点计算而已
*/

#include<cstdio>

const int MAXN = 101;
const double DINF = 1e100;

double q[MAXN],dp[MAXN],c[MAXN];

int main()
{
    int n;
    for(double ts,t;~scanf("%d%lf%lf",&n,&t,&ts);)
    {
        for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
        for(int i=1;i<=n;i++)scanf("%lf",&c[i]);
        dp[n+1]=0;
        for(int i=n;i;i--)
        {            
            double sum = t+c[i]+q[i]*ts+(1-q[i])*dp[i+1];//c[i]
            double inc = q[i];//记录与k有关的
            double p = 1-q[i];
            dp[i]=sum;
            for(int k=2;i+k<=n+1;k++)
            {
                sum=sum-p*dp[i+k-1]+p*q[i+k-1]*(dp[i+k-1]+ts)+p*(1-q[i+k-1])*dp[i+k]+inc*ts+c[i+k-1];
                inc+=p*q[i+k-1];
                p*=(1-q[i+k-1]);
                if(sum<dp[i])dp[i]=sum;
            }
            dp[i]/=(1-q[i]);
        }
        printf("%.2f\n",dp[1]);
    }
    return 0;
}