模拟考试 9.16 (期望dp)

自动取款机

【问题描述】
小沈阳在小品里说过：“人生最痛苦的事情是人死了，钱还没花了”。
于是小宋（80岁）决定要将所有的储蓄从ATM机中取出花光。 小宋忘记了她有多少存款（银行卡密码她是记得的2333），这个奇怪的ATM不支持查询存款余额功能。小宋知道她存款的唯一信息是存款上限是K元，这意味着小宋的存款x是0到K之间的随机整数（包括K）。
每次小宋都可以尝试从ATM中拿出一些钱。 如果她要取的y元钱不大于她的存款，ATM将立即给小宋y元。 但如果她的存款小于y，小宋将收到ATM的警告。
如果小宋被警告超过w次，那么她将被警方带走，作为小偷。
小宋希望取钱次数期望最小。
由于小宋聪明，她总是采取最好的策略。
请计算小宋将所有储蓄从自动取款机中取出期望次数最小值是多少，并不得被警方带走。
【输入格式】
每个测试点包含多组测试数据（最多10组）
每组测试数据包含两个整数K，和W
1≤K,W≤2000
【输出格式】
对于每组测试数据输出取钱次数最小的期望值，舍入到小数点后6位。
【样例输入】
1 1
4 2
20 3

【样例输出】
1.000000
2.400000
4.523810
然而她并不知道赵本山说了：“人生最最痛苦的事情是人活着呢钱没了”。。。
这是个悲伤的故事。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
const int maxn=2002;
double dp[maxn][15];//dp[i][j]表示还剩0~i元,被警告j次的最优期望步数。
int main(){
     freopen("atm.in","r",stdin);
     freopen("atm.out","w",stdout);
     for(int i=1;i<=maxn;++i) dp[i][0]=2147483640;
     for(int i=1;i<=12;++i) dp[0][i]=0;
     for(int i=1;i<=maxn;++i)
       for(int j=1;j<=12;++j){
             dp[i][j]=2147483640;
            for(int k=1;k<=i;++k) 
             dp[i][j]=min(dp[i][j],double(i-k+1.0)/(i+1.0)*dp[i-k][j]+double (k)/(i+1.0)*dp[k-1][j-1]+1);//这步的期望等于这步未被警告的加上被警告的啊哈？ 
       }
     while(scanf("%d%d",&n,&m)==2) printf("%.6lf\n",dp[n][min(11,m)]);
    return 0;
}