【poj3744】 Scout YYF I
2024-10-13 18:02:10
http://poj.org/problem?id=3744 (题目链接)
题意
给出n个雷,分别在 a[1]...a[n] ,走一步概率为 p ,走两步概率为 1-p ,一开始在 1 号位置,问安全到达终点的概率。
Solution
很显然的dp:f[i]=p*f[i-1]+(1-p)*f[i-2]。考虑a[i]位置上有雷,那么安全通过的概率也就是到达f[a[i]+1]的概率为:f[a[i]-1]*(1-p)。
因为a[i]很大,所以要分段用矩阵快速幂。
细节
代码能力下降的厉害。。。莫名Wa了的可以去看看Discuss,好坑。。
代码
// poj3744 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 1<<30 #define eps 1e-8 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; double tmp[2][2],f[2][2],t[2][2],p; int a[20],n; void power(int k) { t[0][0]=p,t[0][1]=1,t[1][0]=1-p,t[1][1]=0; while (k) { if (k&1) { for (int i=0;i<=1;i++) for (int j=0;j<=1;j++) { tmp[i][j]=0; for (int k=0;k<=1;k++) tmp[i][j]+=f[i][k]*t[k][j]; } memcpy(f,tmp,sizeof(f)); } k>>=1; for (int i=0;i<=1;i++) for (int j=0;j<=1;j++) { tmp[i][j]=0; for (int k=0;k<=1;k++) tmp[i][j]+=t[i][k]*t[k][j]; } memcpy(t,tmp,sizeof(t)); } } int main() { while (scanf("%d%lf",&n,&p)!=EOF) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n);a[0]=0; f[1][1]=1; for (int i=1;i<=n;i++) { f[1][0]=f[1][1]*p; f[0][1]=f[1][0]*p+f[1][1]*(1-p); f[0][0]=f[0][1]*p+f[1][0]*(1-p); if (a[i]-a[i-1]==1) {f[1][1]=0;break;} else if (a[i]-a[i-1]==2) f[1][1]=f[1][1]*(1-p); else if (a[i]-a[i-1]==3) f[1][1]=f[1][0]*(1-p); else if (a[i]-a[i-1]==4) f[1][1]=f[0][1]*(1-p); else power(a[i]-a[i-1]-5),f[1][1]=(1-p)*f[0][0]; } if (fabs(f[1][1])<eps) puts("0.0000000"); else printf("%.7lf\n",f[1][1]); } return 0; }
最新文章
- Backbone中的model和collection在做save或者create操作时, 如何选择用POST还是PUT方法 ?
- 移动端横屏(beta)
- (转)Oracle 在Drop表时的Cascade Constraints
- 使用kuernetes提供高可用的kibana服务
- Javascript题库
- Linux -- 文件统计常用命令
- 重叠I/O之可等待的重叠I/O【系列一】
- 关于负数的isdigit()判断
- [ An Ac a Day ^_^ ] hdu 1662 Trees on the level 数据结构 二叉树
- SVN ---文件加锁,执行clean up命令
- ios系统判断某些适配 __IPHONE_OS_VERSION_MAX_ALLOWED
- EXT.NET复杂布局(二)——报表
- Django 学习笔记(四)模板变量
- sqlserver 以年月日为条件查询记录
- vue页面固定锁死
- IOS Javascript Date的坑
- centos 7安装java开发环境
- 404 Note Found 队-Beta1
- UIScrollView增加回弹效果
- 解决pymysql.err.InternalError: (1366, ";Incorrect string value: &#39;\\xF0\\x9F\\x8C\\xB8&#39; for column &#39;headline&#39; at row 1";)