http://acm.hdu.edu.cn/showproblem.php?pid=5236
题意：
现在有人要在文本编辑器中输入n个字符，然而这个编辑器有点问题。
在i+0.1s（i>=0）的时刻可以输入一个字符。
在i+0.9s（i>0）的时刻系统可能会崩溃，需要重新开始或者从上次保存点开始。
在i时刻可以选择保存，保存需要按x个键（假设按键速度极快）。最后完成时必须保存一下。
现在要你来确定一个最佳的输入策略，使得最后按键的期望值最小。
思路：
首先不考虑保存的情况：
则输入第i个字符的期望值为：$dp[i] = dp[i-1] + p*(1+dp[i]) + (1-p)$。化简后得：$dp[i]=(dp[i-1]+1)/(1-p)$。
接下来考虑保存的情况，可以猜想尽量的把保存点安排的均匀一些，即每输入k或k+1个字符就保存一次。那么可以枚举保存的次数，取最小值。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e5+; int n, x;
double p;
double dp[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int T;
int cas = ;
scanf("%d",&T);
while(T--)
{
scanf("%d%lf%d",&n,&p,&x);
for(int i=;i<=n;i++)
dp[i] = (dp[i-]+)/(-p);
double ans = 0x3f3f3f3f;
for(int i=;i<=n;i++)
{
int k = n/i;
int r = n%i;
ans = min(ans, r*dp[k+] + (i-r)*dp[k] + i*x);
//将剩余的r个字符分配到r块中，那么这r块需要敲k+1个字符
//剩余的i-r块则只需要敲k个字符
}
printf("Case #%d: %.6f\n", ++cas, ans);
}
return ;
}