题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=5236
题意：打印一篇论文需要按键n次，在每i+0.1秒时打，在第i+0.9秒时有p的概率系统崩溃，崩溃后需要回退到开头或上次保存的地方重新开始。可以选择在第i秒时按下x个键保存，打完所有之后也需要保存一次。求打印整篇文章需要按键的个数的期望。
提供一组数据：
input：
10
7 0.27 3
18 0.57 2
14 0.4 17
7 0.14 4
19 0.83 2
18 0.13 16
13 0.18 8
7 0.88 5
13 0.9 3
12 0.29 2
output：
Case #1: 21.155284
Case #2: 77.860465
Case #3: 119.728395
Case #4: 17.386852
Case #5: 149.764706
Case #6: 70.493621
Case #7: 45.449260
Case #8: 93.333333
Case #9: 169.000000
Case #10: 32.353105
大体思路：
在没有保存情况时，设f[i]表示打前i个字符所需的按键数的期望，可以得到
f[i] = p * (1 + f[i-1] + f[i]) + (1 - p) * (1 + f[i-1])
上式即表示有p的概率崩溃，崩溃时即从i - 1处再按一次键再回到原处重新进行f[i]次按键，或有(1 - p)的概率不崩溃，直接从f[i - 1]转移来。
化简后可得f[i] = (1 + f[i-1) / (1 - p)。
再考虑中间保存的情况。
枚举一共保存的次数i，这样即每按打n/i个字符或打n/i+1个字符保存一次。连续打n/i个字符所需的按键期望为f[n/i]。
注意：本题要求精确到小数点后6位，如果多输出小数点后的位数会判为WA（或许没写spj）。
代码：
#include <bits/stdc++.h>using namespace std;#define ll long long
#define ull unsigned long long
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)const int maxn = 5e5 + 10;double f[maxn];
int n, x;
double p;int main() {__;int _;cin >> _;for (int sce = 1; sce <= _; ++sce) {cin >> n >> p >> x;for (int i = 1; i <= n; ++i)f[i] = (1.0 + f[i - 1]) / (1.0 - p);double ans = 1e100;for (int i = 1; i <= n; ++i) {ans = min(ans, f[n / i + 1] * (double) (n % i) + f[n / i] * (i - n % i) + i * x);}cout << "Case #" << sce << ": " << fixed << setprecision(6) << ans << endl;}return 0;
}
