多校5 1001 HDU5781 ATM Mechine 记忆化搜索+概率

// 多校5 1001 HDU5781 ATM Mechine
// http://acm.hdu.edu.cn/search.php?field=problem&key=2016+Multi-University+Training+Contest+5&source=1&searchmode=source
// 记忆化搜索
// 每次二分，决策最优，所以最多查询11次
// dp[i][j] 当前能确定i元情况下，还能被警告j次
// 下次取k，实际剩余t
// dp[i][j]=min(1≤k≤i)({(∑(0≤t<k)dp[k?1][j-1]+∑(k≤t≤i)dp[i?k][j])/(i+1)})+1=(min(1≤k≤i){k*dp[k?1][j-1]+(i?k+1)*dp[i?k][j]})/(i+1)+1
// k=0 没有钱可以取，当然次数为0
// w=0 这种情况要排除
// w=1 最后只能1块的取，直到取完，警告没有钱可以取了


// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
const double inf = 0x3f3f3f3f;
#define lson l,mid,rt<<1
// #define rson mid+1,r,rt<<1|1
const int N = 2010;
const int M = 1e6+10;
const int MOD = 1e9+7;
#define LL long long
#define LB long double
// #define mi() (l+r)>>1
double const pi = acos(-1);
const double eps = 1e-8;
void fre(){freopen("in.txt","r",stdin);}
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}

double dp[2010][11];
bool vis[2010][11];
double dfs(int k,int x){
    double ans=inf;
    if(k==0) return 0;
    if(x==0) return inf;
    if(x==1) return (double)((1 + k + 1) * (k + 1) / 2 - 1) / (k + 1);
    if(vis[k][x]) return dp[k][x];
    for(int i=1;i<=k;i++){
       ans=min(ans,1.0*(k-i+1)/(k+1)*dfs(k-i,x)+1.0*i/(k+1)*dfs(i-1,x-1)+1);
    }
    vis[k][x]=true;
    return dp[k][x]=ans;
}

int main(){
    int k,w;
    while(~scanf("%d%d",&k,&w)){
        double ans=dfs(k,min(w,11));
        printf("%.6f
",ans);
    }
    return 0;
}