【题意】：
一篇文章n个字符，每打一个字符（包括退格）需要1个单位时间。时不时可以用t个时间去检查错误发现错误，用退格键退到第一个错误的地方，然后重新打。给出每个字符错误的概率，问打完这篇文章所需最小时间的期望。
【题解】：设dp[i]表示前i个字符已经正确打完，从第i+1个字符到结束所需的最小时间的期望。
显然有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] 是错误的概率。
转移的意思是：一次过打k个字符，然后用 t 时间去检查，最后用退格键退回到第一个错误的位置。
注意这个转移方程，很容易发现这是O(n*n*n)的。
从哪个开始打起 i
一次打了多少个 j
第一个错误的位置 k
O(n*n*n)的做法明显会TLE的，但是利用数学知识，我们可以化简掉一维。最终的时间复杂度为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