2016多校训练Contest5:1001 ATM Mechine

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5781

题目翻译

Alice 有在 [0,K] 区间随机的存款。
每次 Alice 可以对ATM机取 M 元钱 ,如果 M 大于 Alice 当前真实积蓄那么 Alice 会得到ATM机的警告(如果 Alice 得到大于W次警告,Alice 将会被带走,这是不允许的),如果 M 小于等于 Alice 当前真实积蓄那么 Alice 将会取出 M 元钱。
请问 Alice 在不被带走的情况下,取出 所有积蓄 的期望取钱次数是多少。

题解

很明显,Alice 用二分法可以最快的取出积蓄,而二分法的最多警告次数是 logN 次,所以W最多不超过15。
我们用 E[K,W] 表示当前继续在 [0,K] 区间,可以警告次数为 W .
对于 E[K,W] ,我们穷举尝试出去的钱 M 属于[1,K]。
E[K,W] = min( E[k,W] ,  (K-M+1)/(K+1)E[K-M,W] + M/(K+1)E(M-1,W-1) +1 ) 即为(成功提款期望 + 失败提款期望 + 本次操作)的最小值
边界条件

  1. K=0 时 , E[K,W]=0 表示确定没有存款
  2. K!=0 && W=0 时 ,E[K,W]=INF 表示无法确定存款

代码