2016多校训练Contest5：1001 ATM Mechine
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5781
题目翻译
Alice 有在 [0,K] 区间随机的存款。
每次 Alice 可以对ATM机取 M 元钱 ，如果 M 大于 Alice 当前真实积蓄那么 Alice 会得到ATM机的警告（如果 Alice 得到大于W次警告，Alice 将会被带走，这是不允许的），如果 M 小于等于 Alice 当前真实积蓄那么 Alice 将会取出 M 元钱。
请问 Alice 在不被带走的情况下，取出 所有积蓄 的期望取钱次数是多少。
题解
很明显，Alice 用二分法可以最快的取出积蓄，而二分法的最多警告次数是 logN 次，所以W最多不超过15。
我们用 E[K,W] 表示当前继续在 [0,K] 区间，可以警告次数为 W .
对于 E[K,W] ，我们穷举尝试出去的钱 M 属于[1,K]。
E[K,W] = min( E[k,W] , (K-M+1)/(K+1)E[K-M,W] + M/(K+1)E(M-1,W-1) +1 ) 即为（成功提款期望 + 失败提款期望 + 本次操作）的最小值
边界条件
- K=0 时 , E[K,W]=0 表示确定没有存款
- K!=0 && W=0 时 ，E[K,W]=INF 表示无法确定存款
代码
|
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 |
/* Author : WNJXYK Problem : 1001 Blog : http://wnjxyk.cn Date : 2016.8.2 */ #include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<set> #include<vector> #include<map> using namespace std; const int Maxn=2000; const double Inf=1e12; double E[Maxn+5][15+5]; bool F[Maxn+5][15+5]; double DP(int k,int w){ if (k==0) return 0; if (w==0) return Inf; if (F[k][w]) return E[k][w]; F[k][w]=true; E[k][w]=Inf; for (int i=1;i<=k;i++){ double rate=1.0; //No Warning rate += (double)(k-i+1)/(double)(k+1)*DP(k-i,w); //Warning rate += (double)(i)/(double)(k+1)*DP(i-1,w-1); E[k][w] = min(E[k][w],rate); } return E[k][w]; } int W,K; inline void solve(){ memset(F,false,sizeof(F)); printf("%.6lf\n",DP(K,min(15,W))); } int main(){ //freopen("in.txt","r",stdin); while(scanf("%d%d",&K,&W)!=EOF) solve(); return 0; } |
原文链接：2016多校训练Contest5：1001 ATM Mechine
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!