简单概率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 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\n",dp[f]);
}
return 0;
}
上一篇:hdu 3853 LOOPS(概率 dp 期望)


下一篇:拆分Cocos2dx 渲染项目 总结