简单概率dp(期望)-zoj-3640-Help Me Escape

题目链接：

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 11000double 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\n",dp[f]);    }   return 0;}