首页 > 代码库 > zoj 3640 Help Me Escape(期望)
zoj 3640 Help Me Escape(期望)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4808
被这道题坑惨了。
有一个吸血鬼被困了,有n条路可以逃出去,每条路有一个难度c[],他初始的战斗力是f,对于第i条路,若f > c[i]他花t[i]天就能出去,否则,他就停留一天,同时战斗力增加c[i]然后再选一条路走出去,他走每条路的概率是相同的。问他逃出去的天数的期望。
设dp[i]表示在战斗力为i时逃出去的期望值,那么可推出状态方程
dp[i] = 1/n * t[j](c[j] > i),dp[i] = 1/n * (1+dp[ i+c[j] ] )( c[j] <= i)。
需要注意的是终态的确定。当f > Max时,这时的期望值为总时间的平均值便是终态了,但是i + c[j]有可能大于Max+1,所以终态应该是Max*2。初始化时就忘乘2了。
还有就是t[i]是整数。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> //#define LL __int64 #define LL long long #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; double dp[10010]; int c[110]; double t[110]; int main() { int n,f; int Max; double sum_t,ave_t; while(~scanf("%d %d",&n,&f)) { Max = f; sum_t = 0; for(int i = 1; i <= n; i++) { scanf("%d",&c[i]); t[i] = (int) ( (1+sqrt(5))*0.5*c[i]*c[i] ); Max = max(Max,c[i]); sum_t += t[i]; } ave_t = sum_t/n; if(f > Max) { printf("%.3lf\n",ave_t); continue; } memset(dp,0,sizeof(dp)); for(int i = Max+1; i <= 20000; i++) dp[i] = ave_t; for(int i = Max; i >= f; i--) { for(int j = 1; j <= n; j++) { if(i > c[j]) { dp[i] += t[j]; } else { dp[i] += 1+dp[i+c[j]]; } } dp[i] /= n; } printf("%.3lf\n",dp[f]); } return 0; }
zoj 3640 Help Me Escape(期望)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。