/*
    這道題是請(qǐng)教了watashi神牛才懂的，真的是神牛做題如切菜~~~
    題意：一篇文章n個(gè)字符，每打一個(gè)字符（包括空格）需要1個(gè)單位時(shí)間。時(shí)不時(shí)可以用t個(gè)時(shí)間去檢查錯(cuò)誤
          發(fā)現(xiàn)錯(cuò)誤，用空格退到第一個(gè)錯(cuò)誤的地方，然后重新打
          給出每個(gè)字符錯(cuò)誤的概率，問打完這篇文章所需最小時(shí)間的期望

    最小時(shí)間，肯定有一個(gè)選擇的過程，用DP解決。還有，期望題一般設(shè)的是當(dāng)前狀態(tài)離結(jié)束的代價(jià)

    設(shè)dp[i]表示i之前的單詞已經(jīng)正確打完了，從i開始到結(jié)束還需要的時(shí)間
    初始dp[n+1]=0 答案就是dp[0]了
    枚舉從i開始打完k個(gè)字符后就檢查
    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]是錯(cuò)誤的概率
    意思是：一口氣打了k個(gè)，然后用t時(shí)間檢查。檢查的結(jié)果就是哪個(gè)是第一個(gè)錯(cuò)誤的（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有關(guān)的
            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  跟上面類似，多了一點(diǎn)計(jì)算而已
/*
    跟sgu 422 類似 多了一點(diǎn)計(jì)算而已
*/

#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有關(guān)的
            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;
}