HDOJ 5781 ATM Mechine

最近练习概率DP和计算的还是有用的啊，知道经典思路是什么了

题目链接：HDOJ5781

说说题意吧：有一本存折，忘记了有多少钱，只记得钱数不超过K

现在有M次猜测的机会，必须要确定存折中有多少钱！

确定一个词，理解好了，这个题就好了。这样理解确定：

如果现在钱数不超过T，取一块钱都取不出来了，那么就确定存折里面没有钱了

如果现在钱数为1，取1块钱取出来了，那么就确定存折里面没有钱了（因为所有钱都已经取出来了）

确定一词，是用来确定边界情况的

所以，这个题的方法就是枚举：枚举所有的可能猜测的值（从1枚举到K），当然，有的取得出来，有的取不出来

日常概率的经典做法就是分类：

dp【i】【j】为现在钱数不超过i，还有j次猜测的情况下的期望

如果假设当前情况下钱数我要取K，那么有两种情况：

取得出来：说明钱数上限比K大，那么是由dp【i-k】【j】过来的，概率是（i-k+1）/（i+1），分子是说k，k+1，k+2，……i，都符合，分母是说0，1,2，……i

取不出来：说明钱数上限不足K，那么上限为K-1（还是不确定有多少钱），用过了一次猜测的机会，概率是k/（i+1），那么是由dp【k-1】【j-1】过来的

k是多少呢？不知道，所以需要枚举

这样看，i，j，k三个变量，三重循环，都是需要枚举的，复杂度是O（K^2*W），会超时

那么，想想，W是不需要那么搞的，因为最好的方法是二分，就可以减去一半的枚举量，也就是说：

最多的枚举次数是：O（logK），K最大是2000，那么j最大是12咯

所以可以用上面的方法打表，而且减小时间复杂度

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxw=12;
const int mod=1e9+7;
double dp[2333][15];
const double eps=1e-8;
const double INF=1e9;
int main(){
	//freopen("input.txt","r",stdin);
	for(int i=0;i<=2000;i++)
		for(int j=0;j<=maxw;j++){
			dp[i][j]=INF;
			if (i==0) dp[i][j]=0;
			else if (j>0){
				for(int k=1;k<=i;k++)
					dp[i][j]=min(dp[i][j],(i+1-k)*1.0/(i+1)*dp[i-k][j]+k*1.0/(i+1)*dp[k-1][j-1]);
				dp[i][j]+=1;
			}
		}
	int k,w;
	while(scanf("%d%d",&k,&w)!=EOF){
		w=min(w,maxw);
		printf("%.6lf\n",dp[k][w]);
	}
	return 0;
}