/*
    這道題是請教了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;
}