6/12
2016 Multi-University Training Contest 5
期望+记忆化DP A ATM Mechine（BH）
题意：
去ATM取钱，已知存款在[0,K]范围内，每一次输入取出钱的金额，如果大于存款，ATM会发出警报，最多W次，问能在W次内取出所有存款的取款次数的期望值。
思路：
设dp[k][w]表示范围存款在[0,k]内，还有w次报警机会的期望值。状态转移方程：
代码：
#include <bits/stdc++.h> const int N = 2e3 + 5;
const int INF = 0x3f3f3f3f;
const int D = 16;
double dp[N][D];
bool vis[N][D]; double DP(int k, int w) {
if (k == 0) return 0;
if (w == 0) return INF;
if (vis[k][w]) return dp[k][w];
double &ret = dp[k][w] = INF;
for (int i=1; i<=k; ++i) {
ret = std::min (ret, DP (i-1, w-1)*i/(k+1) + DP (k-i, w)*(k-i+1)/(k+1) + 1);
}
vis[k][w] = true;
return ret;
} int main() {
int k, w;
while (scanf ("%d%d", &k, &w) == 2) {
printf ("%.6f\n", DP (k, std::min (w, 15)));
}
return 0;
}