hdu5781ATM Mechine（概率dp）

本文主要是介绍hdu5781ATM Mechine（概率dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

已知ATM机中有最多n元钱,每次可以从ATM机中请求取出任意多的钱,若钱数足够则能成功取出,否则会受到一次警告.如果警告次数超过m次就会被当做小偷抓走.求在保证不能被抓走的前提下,若采取最优策略,期望多少步能够取走所有的钱.

这题最优主要是采用一个二分的策略 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}max​k=1​i​​​i+1​​i−k+1​​∗E(i−k,j)+​i+1​​k​​∗E(k−1,j−1)+1 这样时间复杂度是O(K^2W)O(K​2​​W)的。 假如Alice使用的是二分策略，那么在最坏情况下至多被警告\left \lceil log_{2}{K} \right \rceil⌈log​2​​K⌉ 次。 于是W:=min(W,15)就可以了。

AC代码：

#include<stdio.h>
#include<iostream>
#include<map>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2200;
const int inf=0x3f3f3f3f;
double dp[maxn][30];
int main(){int k,w;for(int i=1;i<maxn;i++)dp[i][0]=inf;for(int i=0;i<=20;i++)dp[0][i]=0;for(int i=1;i<2010;i++){for(int j=1;j<20;j++){double t=inf;for(int k=1;k<=i;k++){t=min(t,(i-k+1.0)/(i+1)*dp[i-k][j]+k/(i+1.0)*dp[k-1][j-1]+1);}dp[i][j]=t;    }}while(~scanf("%d%d",&k,&w)){printf("%.6lf\n",dp[k][min(w,11)]);}
}

这篇关于hdu5781ATM Mechine（概率dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---