【解题报告】 ZOJ 3640 Help Me Escape - 期望dp

题意：吸血鬼在一个洞穴遍地的地方，他拥有初始战斗力，如果战斗力大于了洞穴的c值（ fighting capacity ）他就能花时间逃出去（有公式计算），否则他的战斗力增加c，然后随机选择下一个要去的洞穴，问他能出去所花时间的期望是多少。

考虑期望的递推关系，E(i)表示战斗力为i时的期望。

那么E(i) = ( E(i+c1) + E(i+c2) + ... + E(i+cn) ) / n;

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#define CLR(c,v) memset(c,v,sizeof(c))
using namespace std;

const int N = 2e4 + 5;
const int INF =  (1<<30);
const int inf = -(1<<30);
const double C = (sqrt(5.0)+1.0) * 0.5;

double ans[N];
int n,c[N],T[105];

double Ef(int f){ // Ef(f)  表示能力值（Cain fighting capacity）为f时 期望为Ef(f)
	// 算期望一般是从后往前推，因为我们要最终状态的期望，往往要考虑最终状态能由那些状态到达，
	// 将那些状态求和取平均值，然后那些状态依次递归求解即可
	// 递归的深度为ci的最大值（maybe cave's some capacity）10000
	
	if(ans[f] > 0)	return ans[f];
	for(int i = 0 ; i < n ; i++){
		if(f > c[i])
			ans[f] += T[i]*1.0 / n;
		else
			ans[f] += (1.0+Ef(f+c[i])) / n;
	}
	return ans[f];
}
void solve(int mmax,int f){
	for(int i = mmax + 1 ; i >= f ; i--){
		for(int j = 0 ; j < n ; j++)
			if(i > c[j])
				ans[i] += floor(C * c[j] * c[j]) / n;// floor 容易超时
			else
				ans[i] += (i+c[j] < mmax+1 ? 1+ans[i+c[j]] : 1+ans[mmax+1]) /n; 
	}
}
int main(){
	//freopen("in.txt","r",stdin);
	int f;
	while(cin >> n >> f){
		CLR(ans,0);
		int mmax = f;
		for(int i = 0; i < n ; i++){
			scanf("%d",&c[i]);
			mmax = mmax>c[i] ? mmax : c[i];
		}
		for(int i = 0; i < n ; i++)
			T[i] = floor(C*c[i]*c[i]);
		//solve(mmax,f); printf("%.3f\n",ans[f]);
		printf("%.3f\n",Ef(f));
	}

	return 0;
}