hdu5781ATM Mechine+數學期望

Problem Description

Alice is going to take all her savings out of the ATM(Automatic Teller Machine). Alice forget how many deposit she has, and this strange ATM doesn’t support query deposit. The only information Alice knows about her deposit is the upper bound is K RMB(that means Alice’s deposit x is a random integer between 0 and K (inclusively)).

Every time Alice can try to take some money y out of the ATM. if her deposit is not small than y, ATM will give Alice y RMB immediately. But if her deposit is small than y, Alice will receive a warning from the ATM.

If Alice has been warning more then W times, she will be taken away by the police as a thief.

Alice hopes to operate as few times as possible.

As Alice is clever enough, she always take the best strategy.

Please calculate the expectation times that Alice takes all her savings out of the ATM and goes home, and not be taken away by the police.

Input

The input contains multiple test cases.

Each test case contains two numbers K and W.

1≤K,W≤2000

Output

For each test case output the answer, rounded to 6 decimal places.

Sample Input

1 1

4 2

20 3

Sample Output

1.000000

2.400000

4.523810

Author

ZSTU

Source

2016 Multi-University Training Contest 5

題目意思：Alice忘記了自己銀行裡存了多少錢，隻記得在［0，k］之間。每次取錢如果餘額足夠就出錢，否則警告一次，警告超過w次就會把你抓起來，在不想被警察抓起來的前提下，Alice采取最優政策，求期望取錢多少次能知道自己存了多少錢。

官方給出的題解

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const double inf=;
double f[][];  //最多的錢，剩餘可用的次數

double bank(int m,int w){
    if(m==) return ;
    if(w==) return inf;
    if(f[m][w]>) return f[m][w];

    double ans=inf;
    for(int i=;i<=m;i++){  //枚舉實際的錢數
        ans=min(ans,bank(i-,w-)*i/(m+)+bank(m-i,w)*(m-i+)/(m+)+);
        //為什麼加1.。考慮的很久，菊苣已解釋貌似就知道了。
        //試了一次之後，産生了兩種步數期望，還要加上我試的這一次。
        //orz巨啊。。。
    }
    return f[m][w]=ans;
}

int main(){
    int k,w;
    fill(f[],f[]+ * ,);
    while(scanf("%d %d",&k,&w)!=EOF){
        w=min(w,);//為什麼15呢？因為二分查找2^15>2000
        printf("%.6f\n",bank(k,w));
    }
    return ;
}