概率DP。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } double dp[2010][20]; void init() { for(int i=1;i<=2000;i++) for(int j=0;j<=15;j++) dp[i][j]=999999; for(int i=0;i<=15;i++) dp[0][i]=0; for(int i=1;i<=2000;i++) for(int j=1;j<=15;j++) for(int x=1;x<=i;x++) dp[i][j]=min(dp[i][j],1.0*(i-x+1)/(i+1)*dp[i-x][j]+1.0*x/(i+1)*dp[x-1][j-1]+1); } int main() { int w,k;init(); while(~scanf("%d%d",&w,&k)) { printf("%.6lf ",dp[w][min(k,15)]); } return 0; }