首页 > 代码库 > zoj3640 Help Me Escape
zoj3640 Help Me Escape
ZOJ - 3640
Help Me Escape
题目大意：
Cain被困在一个洞穴里，洞穴有n个出口，每个出口有一个难度值C[i]，Cain有一个初始的战斗值f。现在Cain随机选择一个出口，如果f大于出后的难度，那么Cain将会花floor( (1+sqrt(5))/2*C[i]*C[i] )天出去，否则Cain的f将会增加C[i]并且消耗掉一天时间，然后重新尝试。求Cain逃出洞穴天数的期望值。。。
#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>using namespace std;int n,m,c[110],t[110];double dp[20001];bool vis[20001];double dfs(int f){ if(vis[f])return dp[f]; double ans=0; for(int i=1;i<=n;i++){ if(f>c[i])ans+=1.0/n*t[i]; else ans+=1.0/n*(1+dfs(f+c[i])); } vis[f]=1; return dp[f]=ans;}int main(){ double tmp=sqrt(5.0); while(scanf("%d%d",&n,&m)!=EOF){ memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++)t[i]=(int)((1+tmp)/2*c[i]*c[i]); dfs(m); printf("%.3lf\n",dp[m]); }}
/* 设dp[i]表示能力值为i时，逃离的期望值。*/#include<iostream>#include<cstring>#include<cmath>#include<cstdlib>#include<cstdio>using namespace std;int n,m,c[110],t[110],mx;double dp[20001];int main(){ freopen("Cola.txt","r",stdin); double tmp=sqrt(5.0); while(scanf("%d%d",&n,&m)!=EOF){ memset(dp,0,sizeof(dp));mx=0; 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+tmp)/2*c[i]*c[i]); for(int i=mx+mx;i>=m;i--){ for(int j=1;j<=n;j++){ if(i<=c[j])dp[i]+=1.0/n*(1+dp[i+c[j]]); if(i>c[j])dp[i]+=1.0/n*t[j]; } } printf("%.3lf\n",dp[m]); }}
zoj3640 Help Me Escape
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。