首页 > 代码库 > zoj3640（概率dp）
zoj3640（概率dp）
题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4808
题意： 一个吸血鬼，每次可以随机的选择n个洞中的任意一个，如果该吸血鬼的攻击值大于 该洞c[i]那么直接可以花费t[i]的时间久可以出去，不然要奋斗一天该吸血鬼攻击值在增加c[i] 随机选择n个洞口。
分析：dp[i]表示攻击力为i时逃出去的期望值，从后往前递推到f即可。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 1000010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double t[110];int c[110];double dp[N];int main(){ int n,f; while(scanf("%d%d",&n,&f)>0) { int mx=f; for(int i=1;i<=n;i++)scanf("%d",&c[i]),mx=max(mx,c[i]); for(int i=1;i<=n;i++)t[i]=(int)((1+sqrt(5))*0.5*c[i]*c[i]); for(int i=2*mx;i>=f;i--) { double p=0; for(int j=1;j<=n;j++) { if(i>c[j])p+=t[j]; else p+=1+dp[i+c[j]]; } dp[i]=p/n; } printf("%.3lf\n",dp[f]); }}
zoj3640（概率dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。