HDU 5236 Article（概率DP）

 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+5;

int n, x;
double p;
double dp[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    int T;
    int cas = 0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%lf%d",&n,&p,&x);
        for(int i=1;i<=n;i++)
            dp[i] = (dp[i-1]+1)/(1-p);
        double ans = 0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            int k = n/i;
            int r = n%i;
            ans = min(ans, r*dp[k+1] + (i-r)*dp[k] + i*x);
            //将剩余的r个字符分配到r块中，那么这r块需要敲k+1个字符
            //剩余的i-r块则只需要敲k个字符
        }
         printf("Case #%d: %.6f
", ++cas, ans);
    }
    return 0;
}