应该是machine
和POJ3783 Balls类型相似。
现在上界为i元，猜错次数最多为j时，开始猜测为k元，有两种情况：
1 猜中：(i - k + 1) * dp[i - k][j]
2 猜不中 k * dp[k - 1][j - 1]
两种情况的均值即为第一次猜测为k时的期望，1 <= k <= i + 1，枚举k，取最小值。
另外其实m取不到2000，由二分思想最多十几次(开始也没想到，一直不能把n^3的复杂度降下来)。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 2010, INF = 0x3F3F3F3F;
#define MS(a, num) memset(a, num, sizeof(a))
#define PB(A) push_back(A)
#define FOR(i, n) for(int i = 0; i < n; i++)
double dp[N][20];
void solve(int n, int m){
for(int i = 0; i <= m; i++){
dp[0][i] = 0;
}
for(int i = 1 ; i <= n; i++){
dp[i][0] = INF;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = INF;
for(int k = 1; k <= i + 1; k++){
dp[i][j] = min(dp[i][j], (k * dp[k - 1][j - 1] + (i - k + 1) * dp[i - k][j] ) / (i + 1) + 1);
}
}
}
}
int main(){
solve(2008, 15);
int k, w;
while(~scanf("%d %d", &k, &w)){
w = min(w, 15);
printf("%.6f
", dp[k][w]);
}
return 0;
}