多校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 = ;

 const int M = 1e6+;

 const int MOD = 1e9+;

 #define LL long long

 #define LB long double

 // #define mi() (l+r)>>1

 double const pi = acos(-);

 const double eps = 1e-;

 void fre(){freopen("in.txt","r",stdin);}

 inline int read(){int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;}

 double dp[][];

 bool vis[][];

 double dfs(int k,int x){

     double ans=inf;

     if(k==) return ;

     if(x==) return inf;

     if(x==) return (double)(( + k + ) * (k + ) /  - ) / (k + );

     if(vis[k][x]) return dp[k][x];

     for(int i=;i<=k;i++){

        ans=min(ans,1.0*(k-i+)/(k+)*dfs(k-i,x)+1.0*i/(k+)*dfs(i-,x-)+);

     }

     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,));

         printf("%.6f\n",ans);

     }

     return ;

 }