题目大意&题解
现在取款机里最多有存款k，现在我们不知道取款机里的剩余钱数（但是我们知道剩余钱数的上界），我们每次可以尝试着取钱，如果取的钱大于取款机里的钱数取款机就会警告，如果被警告w次就会被警察带走…问采取最优策略时的期望取款次数。
一开始完全想错了，本来想的是用二分的方法去取钱…（二进制），然而发现第三组样例是错的，感觉是思路有问题。后来查了下题解说是用DP…瞬间就懂了…
我们设\(E(i,j) \)是上界为i时，还可以被警告j次的最优解，那么通过枚举剩余钱数，很好写出转移： \[ E(i,j)=( \sum_{k=1}^n(\frac{i-k+1}{i+1}·E(i-k,j)+\frac{k}{i+1}·E(i-1,k-1)+1 ) )_{min} \]
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int k,w;
double e[2005][2005];
double dfs(int i,int j)
{
if (i==0) return 0;
if (j==0) return e[i][j]=1e9;
if (e[i][j]>0) return e[i][j];
double ret=1000000000000;
for (int k=1;k<=i;k++) ret=min(ret,1.0*(i-k+1)/(i+1)*dfs(i-k,j)+1.0*k/(i+1)*dfs(k-1,j-1)+1.0);
return e[i][j]=ret;
}
int main()
{
while (scanf("%d%d",&k,&w)!=EOF)
{
w=min(w,15);
printf("%.6lf\n",dfs(k,w));
}
return 0;
}