【題意】：一篇文章n個字符，每打一個字符（包括退格）需要1個單位時(shí)間。時(shí)不時(shí)可以用t個時(shí)間去檢查錯誤發(fā)現(xiàn)錯誤，用退格鍵退到第一個錯誤的地方，然后重新打。給出每個字符錯誤的概率，問打完這篇文章所需最小時(shí)間的期望。

【題解】：設(shè)dp[i]表示前i個字符已經(jīng)正確打完，從第i+1個字符到結(jié)束所需的最小時(shí)間的期望。
               顯然有dp[n] = 0，然后最終答案就是dp[0]了。
               枚舉從i+1個字符開始打，打完k個字符就檢查一次。
               dp[i] = min{(t+k) + q[i+1]*(dp[i]+k) + p[i+1]q[i+2]*(dp[i+1]+k-1) + …… + p[i+1]p[i+2]……q[i+k]*(dp[i+k-1]+1) + p[i+1]p[i+2]……p[i+k]*(dp[i+k]) } ，其中 1 <= k <= n - i。
               p[i] 是正確的概率，q[i] 是錯誤的概率。
               轉(zhuǎn)移的意思是：一次過打k個字符，然后用 t 時(shí)間去檢查，最后用退格鍵退回到第一個錯誤的位置。
               注意這個轉(zhuǎn)移方程，很容易發(fā)現(xiàn)這是O(n*n*n)的。
                              從哪個開始打起 i
                                    一次打了多少個 j
                                          第一個錯誤的位置 k
               O(n*n*n)的做法明顯會TLE的，但是利用數(shù)學(xué)知識，我們可以化簡掉一維。最終的時(shí)間復(fù)雜度為O(n*n)。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 3050
 6 int n, t;
 7 double dp[maxn], p[maxn], q[maxn];
 8 
 9 void solve() {
10     dp[n] = 0;
11     for(int i = n - 1; i >= 0; i--) {
12         double c = p[i+1];
13         double sum = t + 1 + q[i+1] + dp[i+1] * p[i+1];
14         dp[i] = sum;
15         for(int j = 2; j <= n - i; j++) {
16             c *= p[i+j];
17             sum = sum + 2 - c + c * dp[i+j] - c * dp[i+j-1];
18             dp[i] = min(dp[i], sum);
19         }
20         dp[i] /= p[i+1];
21     }
22     printf("%.6f\n", dp[0]);
23 }
24 
25 int main() {
26     while(~scanf("%d%d", &n, &t)) {
27         for(int i = 1; i <= n; i++) {
28             scanf("%lf", &q[i]);
29             p[i] = 1 - q[i];
30         }
31         solve();
32     }
33     return 0;
34 }
35