MYF

HDU 5781 ATM Mechine

Posted on | In | | Visitors

题目链接

HDU 5781

题目类型：概率DP

题目来源：2016 Multi-University Training Contest 5

题目分析

题目大意

Alice去取款机取钱，她不记得自己到底有多少余额了，她知道自己的余额在$[0, k]$区间之内。取款机也无法显示余额。取款机还有另外一个毛病——当你取的钱的数量大于你现有的钱的数量的话，就会报警，当报警次数大于$w$次之后，警察就会来把Alice带走。但是Alice足够聪明，每次都会用最少的次数把钱全部取走，问Alice取钱次数的期望值是多少？

解析

首先先考虑最笨的情况下，一次取一块钱，那么直到报警为止，然后把所有的钱都取走。

稍微聪明一点的做法是，按$w$块钱为步长的取，当取到第$kw$块钱无法取的时候，就取$kw-1, kw-2, …$，直到取到能取出的情况为止。

再聪明一点的话，是二分的去取钱。

最聪明的做法是一种接近二分的做法，举个例子，当你的金额上限为$20$元最大报警次数为$3$时，你可以先取$10$块钱，如果取$10$块钱都报警了，那相当于你可以取$9$块钱可以报警两次的情况。如果取$10$块钱没有报警的话，那么就相当于存在一种11~20块钱你可以报错3次的情况。这样就形成了一个DP，$DP[i][j]$状态表示取$0~i$块钱，可以报错$j$次，由此可以写出状态转移方程$dp[i][j] = min (dp[k-1][j-1] + dp[i-k][j] + i + 1)$其中$i+1$表示$0~i$各取一次。根据题解我们可以发现，当报警大于$15$时一定可以达到目的。

官方题解

E(i,j):存款的范围是[0,i],还可以被警告j次的期望值。

E(i,j) = $max{k=1}^{i}{\frac{i-k+1}{i+1} E(i-k,j)+\frac{k}{i+1}E(k-1,j-1)+1}$
这样时间复杂度是$O(K^2W)$的。
假如Alice使用的是二分策略，那么在最坏情况下至多被警告$\left \lceil log{2}{K} \right \rceil$ 次。
于是W:=min(W,15)就可以了。

写题解的时候顺便看看别人的代码，发现有一个更优雅的。传送门

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=2000+5;
const int mod=1000000007;
const ll INF=1e18+10;
const double eps=1e-8;
double dp[maxn][20];
int cnt[maxn];//记录二分的次数
int main(){
    cnt[0]=0;	
    cnt[1]=1;
    for (int i=2; i<maxn; i++) {
        cnt[i] = cnt[ i / 2 - 1 ] + 1;
    }
    for (int i=1; i<maxn; i++) {
        dp[i][1] = (i+1)*(i+2)/2 - 1;
        if (i!=1) {
            cnt[i]++;
        }
        for (int j=2; j<=cnt[i]; j++) {
            dp[i][j] = INF;
            for (int k = 1; k<i; k++) {
                dp[i][j] = min (dp[i][j], dp[k-1][j-1]+ dp[i - k][j] + i + 1);
            }
        }
        for (int j=cnt[i]+1; j<20; j++) {
            dp[i][j] = dp[i][cnt[i]];
        }
    }
    int w,k ;
    while (~scanf("%d%d",&k, &w)) {
        printf("%.6f\n",dp[k][min(19, w)]/(k+1));
    }
}