题目链接：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4808
题目大意:
有n条路，选每条路的概率相等，初始能力值为f,每条路通过的难度值为ci,当能力值大于某条路A的难度值b时，能够成功逃离，花费时间ti,小于等于时，不能逃离但能力值增加b.
给定初始的能力值，求成功逃离的期望。
解题思路：
简单期望dp.
设dp[i]表示能力值为i时，逃离的期望值。
对于每条路j,当i>c[j]时，成功逃离+ti[j],否则能力值加c[j] +1+dp[j+c[j]]).
从后往前递推，求出dp[f],即可。
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3fffffff
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define Maxn 11000
double dp[Maxn<<1],ti[Maxn];
int n,f,cc[Maxn];
int main()
{
while(~scanf("%d%d",&n,&f))
{
int Max=0;
double sum=0.0;
for(int i=1;i<=n;i++)
{
scanf("%d",&cc[i]);
ti[i]=int((1+sqrt(5.0))/2.0*cc[i]*cc[i]); //注意是向下取整
Max=max(Max,cc[i]);
sum+=ti[i]; //总的天数
}
double pp=1.0/n;//每条路的概率
double tmp=pp*sum;//当能力值大于最大的难度时，逃离的期望
for(int i=Max+1;i<=2*Max;i++) //预处理下
dp[i]=tmp;
for(int j=Max;j>=f;j--)
{
double tt=0;
for(int i=1;i<=n;i++)
{
if(j>cc[i]) //能够成功逃离
tt+=pp*ti[i];
else
tt+=(1+dp[j+cc[i]])*pp; //不能够的话，花一天，能力值增加cc[i]
}
dp[j]=tt;
}
printf("%.3lf
",dp[f]);
}
return 0;
}