首页 > 代码库 > zoj3640：概率（期望）dp
zoj3640：概率（期望）dp
题目大意：有一个吸血鬼，初始攻击力为f，每天随机走到n个洞里面，每个洞有一个c[i]，如果他的攻击力f>c[i]
则可以花费t[i] 的时间逃走，否则则花费一天时间使自己的攻击力增加c[i]，求逃走天数的期望
分析：
这道题求期望，，考虑采用概率dp求解
想到的最简单方法就是dp[i][j]表示 第i天，攻击力为j的概率，然后对每一个c进行转移，最后统计答案
但是发现i，j的范围都是10000，n是100 这么做显然是行不通的
于是又可耻的搜了一下题解，发现有一个博主写的期望dp这个概念很不错
令 dp[a]表示 攻击力为 a 后 还需要多少天逃出的期望，那么dp[f]即为答案
注意关键是这个 “还”
状态转移：
如果 a>c[i] 那么显然还需要 t[i]时间逃出
如果 a<=c[i] 那么先要花费一天把攻击力增加a+c[i],然后还要花费的时间就是 dp[a+c[i]]
这样转移方程就很好写了
由于需要从后往前转移，采用记忆化搜索写
开始数组开10010 老是segment fault 后来开到10W过了。。
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>#include<math.h>#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;int n,f;double p;double dp[100010];int c[1110];bool vi[100010];double dfs(int a){ if(vi[a]) return dp[a]; vi[a]=1; for(int i=0;i<n;i++) { if(a>c[i]) dp[a]+=(double)floor(p*c[i]*c[i])/(double)n; else dp[a]+=(1.0+dfs(a+c[i]))/(double)n; } return dp[a];}int main(){ while(scanf("%d%d",&n,&f)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",c+i); } memset(dp,0,sizeof(dp)); memset(vi,0,sizeof(vi)); p=(1.0+sqrt(5.0))/2.0; printf("%.3f\n",dfs(f)); } return 0;}
zoj3640：概率（期望）dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。