首页 > 代码库 > poj 3774 Scout YYF I (矩阵优化的概率DP)
poj 3774 Scout YYF I (矩阵优化的概率DP)
题意: n个雷,分别在a[1]...a[n] ,走一步概率为 p ,走两步概率为 1-p ,一开始在 1 号位置,问安全到达终点的概率。
思路:
将整个过程划分成阶段处理:
1 ~ a[1]
a[1]+1 ~ a[2]
…………
a[n-1]+1 ~ a[n]
那么只要求出每次踩到雷的概率,求反面,再把所有阶段结果连乘就可以了。
ans[i]表示踩中i的概率,那么可推倒出 ans[i]=p*ans[i-1]+(1-p)*ans[i-2]
因为直接暴力求解超时,构造矩阵
关于矩阵乘法 http://blog.csdn.net/lvshubao1314/article/details/26337911
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a[10]; int n; double p; struct Martix { double m[2][2]; }; //Martix A={p,1-p,1,0}; Martix I={1,0,0,1}; Martix multi(Martix x,Martix y) { Martix ans; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { ans.m[i][j]=0; for(int k=0;k<2;k++) ans.m[i][j]+=x.m[i][k]*y.m[k][j]; } return ans; } Martix power(Martix x,int k) { Martix ans=I; while(k) { if(k&1) ans=multi(ans,x); x=multi(x,x); k>>=1; } return ans; } int main() { while(scanf("%d%lf",&n,&p)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } sort(a,a+n); int now=1; double ans=1; Martix A={p,1-p,1,0}; for(int i=0;i<n;i++) { Martix sum=power(A,a[i]-now); now=a[i]+1; ans*=(1-sum.m[0][0]); //printf("%.7f\n",A.m[0][0]); } printf("%.7f\n",ans); } return 0; }
poj 3774 Scout YYF I (矩阵优化的概率DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。