DESCRIPTION 题意： 有存款上限不超过k元钱，若取钱大于剩余，atm会报错，小于就会取走一部分，问在不超过w次报错下，取出所有钱的最小期望。
这道题一开始想到的最小期望，是用二分答案来逼近自己的存款，若报错次数等于w次就gg，即结果为0.我们只需要枚举0-k这样来枚举存款，在对每次进行二分答案，每次的初始概率就是1/k+1。 但是二分并不是最小期望，只能说“老练”“稳妥”“机智”.但是不得不承认我随机选一个可能一次就取走全部储蓄，并通过w次机会知道自己已经取完了，这样更快（注意atm机并不会告诉你当前余额为多少，也就是说就算你取完了也不定知道自己取完了，这是个坑点）. 在此，我们用dp二维数组来表示，第一维i表示我知道了我的存款最大可能是多少（根据自己前面选择的经验），第二维是j还能有j次报错机会. 转移方程里面我们枚举本次取走k元钱，我们知道余额上界为i（i也在枚举哦），那我们有（i-k+1）/（i+1）的几率取得比存款少，即（存款>=k）,注意可能存款是零，所以有i+1种情况.那剩下的概率是报错的概率，你不会拿走任何钱，并且报警机会也少了一次（详见代码）. 备注： 1.dp存的是次数 2.期望是指： 出现这种结果的概率*结果 3.结果在不同的题可能不一样，比如本题为取完钱的次数. 4.本题注意一开始存款上界数据给的是2000，之前说过二分是很笨的办法，所以log2000是15左右（其实更少，比如13），所以机会>15的直接用15的结果即可——最小期望嘛. 5.感谢w1419的讲解
#include<stdio.h> #include<algorithm> using namespace std; const int N=2050; const int inf=210000000; double dp[N][17]; int k,w; int main(){ for(int i=0;i<N;i++) dp[i][0]=inf;//一次机会都没有 for(int i=0;i<17;i++) dp[0][i]=0;//你知道最大是0，你就不需要操作了 for(int i=1;i<N;i++) for(int j=1;j<17;j++){ dp[i][j]=inf; for(int k=1;k<=i;k++) dp[i][j]=min(dp[i][j],(i-k+1.0)/(i+1)*dp[i-k][j]+k/(i+1.0)*dp[k-1][j-1]+1); +1为本次操作次数 } while(~scanf("%d%d",&k,&w)){ w=min(w,13); printf("%0.6lf\n",dp[k][w]); } }