hdu5236

题目

（抄别人的http://www.cnblogs.com/qscqesze/p/4543740.html）要求输入一篇N个字符的文章，对所有非负整数i：
每到第i+0.1秒时可以输入一个文章字符
每到第i+0.9秒时有P的概率崩溃（回到开头或者上一个存盘点）
每到第i秒有一次机会可以选择按下X个键存盘，或者不存
打印完整篇文章之后必须存盘一次才算完成
输入多组N,P,X选择最佳策略使得输入完整篇文章时候按键的期望最小，输出此期望

思路

dp[i]表示敲i个字符的期望，不考虑保存的情况的dp
dp[i]=dp[i-1]+p*(1+dp[i])+(1-p);
化简为： dp[i] = （dp[i-1] + 1) / ( 1- p)
然后贪心枚举保存次数，如果不能均匀分段，那么要利用贪心做成一些是x的段，一些是x+1的段。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;int n,x;
double p;
double dp[100010];int main()
{int T,kase=1;scanf("%d",&T);while(T--){scanf("%d%lf%d",&n,&p,&x);for(int i=1; i<=n; i++) dp[i]=(1+dp[i-1])/(1-p);double ans=0x3f3f3f3f;for(int i=1; i<=n; i++){int cnt=n%i;ans=min(ans,x*i+dp[n/i]*(i-cnt)+dp[n/i+1]*cnt);}printf("Case #%d: %.6lf\n",kase++,ans);}return 0;
}