应该是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 #include #include #include #include #include #include