首页技术正文

HDU5781–ATM Mechine(概率dp)

开发者好妍技术 2022年11月9日

0 收藏 371 点赞 2,694 浏览 661 个字

题意：Alice忘记了自己银行里存了多少钱，只记得在［0，k］之间。每次取钱如果余额足够就出钱，否则警告一次，警告超过w次就会把你抓起来，在不想被警察抓起来的前提下，Alice采取最优策略，求期望取钱多少次能知道自己存了多少钱。

题解：这场比赛彻底gg了，上官方题解了。

题解中的递推式也很好理解，就是P(存款<k)＊E(存款<k) + P(存款≥k)＊E(存款≥k) + 1

比赛时想过这种做法，但是时间复杂度的原因立刻否定了。还是太弱了T^T…

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;const int N = ;
const double INF = 1e12;
double f[N][];double cal(int k, int w)
{
    if (k == ) return ;
    if (w == ) return INF;
    if (f[k][w] > ) return f[k][w];
    double ans = INF;
    for (int i = ; i <= k; ++i) {
        ans = min(ans, cal(i-,w-)*i/(k+) + cal(k-i,w)*(k+-i)/(k+) + );
    }
    return f[k][w] = ans;
}int main(int argc, char const *argv[])
{
    freopen("in", "r", stdin);    int k, w;
    while (~scanf("%d%d", &k, &w)) {
        w = min(w, );
        printf("%.6f\n", cal(k, w));
    }
    return ;
}