ATM Mechine

本文转自：http://blog.csdn.net/queuelovestack/article/details/52096337

题意：

这题的意思还是比较费解的

Alice忘记自己在银行里存了多少钱,只记得是闭区间[0,k]内的一个整数

每次取钱,Alice会取y RMB的钱,如果余额足够则被取出,否则会被警告一次

若警告次数超过w次,Alice就会被警察抓走

在不被警察抓走的前提下,Alice采取最优策略,问期望尝试取钱多少次能够取完Alice存的所有钱

题解：

首先,我们知道ZSTU偏爱dp

那么无疑,此题为概率dp

令dp[i][j]表示Alice知道自己的存款范围是[0,i],还可以被警告j次的期望值

对于当前存款范围[0,i],Alice取y RMB的时候,会面临两种情况:

①余额不足,即 < y

此时会被警告一次

但相对的,我们可以缩小存款范围[0,y-1]

因为y RMB是取不出的,那存款最多为y-1 RMB,这点显然

所以,dp[i][j]与dp[y-1][j-1]有关

②余额足够,即 ≥ y

此时不会被警告

而且还能缩小存款范围[0,i-y]

因为原来存款最多可能有i RMB,现在取走了y RMB,那么最多还剩i-y RMB

所以,dp[i][j]还和dp[i-y][j]有关

再者,我们要先确定一下递推式,P(存款 < y) * E(存款 < y) + P(存款 ≥y) * E(存款 ≥y) + 1

由递推式来看,上述我们已经分析出了E(存款 < y)和E(存款≥y)

那我们还需要再求解一下P(存款 < y)和P(存款≥y)

因为当前存款范围是[0,i],那么,存款可能就是0y-1这y种情况,大于等于y的则是y~i这i-y+1种

那么可以得到状态转移方程

http://img.blog.csdn.net/20160803100016781

貌似官方题解的状态转移方程写错了

另外,Alice采取二分策略,故在最坏情况下至多被警告次

于是W:=min(W,11)就可以了。

【时间复杂度&&优化】

O(K^2*min{W,11})

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PI(A) cout<<A<<endl

#define SI(N) cin>>N

#define SII(N,M) cin>>N>>M

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<x<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 2000 + 9 ;

double dp[MAXN][15];

int K,W;

double IN=1e200;

int main()

{

    Rep(i,1,MAXN-1)

    Rep(j,0,14)

    {

        dp[i][j]=IN;

        if (!j) continue;

        Rep(y,1,i)

        {

            dp[i][j]=min(dp[i][j],dp[i-y][j]*(i+1-y)/(i+1.0)+dp[y-1][j-1]*y/(i+1.0)+1);

        }

    }

    while(SII(K,W))

    {

        if (W>11) W=11;

        //这要用printf 不能用cout 会错

        printf("%f\n",dp[K][W]);

    }

    return 0;

}

RMB

2016 Multi-University Training Contest 5 ATM Mechine

ATM Mechine

题意：

题解：

代码：