首页 > 代码库 > POJ3744 Scout YYF I (概率DP + 矩阵优化)
POJ3744 Scout YYF I (概率DP + 矩阵优化)
题目链接:
http://poj.org/problem?id=3744
题意:
有一段路,路上有n个陷阱,每一次只能向前走一步或者两步,求安全走过这段路的改路
分析:
设dp[i]表示安全走过第i个陷阱的概率
那么dp[i+1]=dp[i]*(1-p(走到第i+1个陷阱))
因为每次只能走一步或者两步,所有安全走过第i个陷阱后的位置一定在a[i]+1;\
其中a[i]表示第i个陷阱的位置
求从a[i]+1,走到a[i+1]的概率的时候我们需要用到矩阵来经行优化
ans[i]表示走到位置i的概率
ans[i] = p*ans[i-1]+(1-p)*ans[i-2];
ans[0]=0,ans[1]=1;
代码如下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 15; double dp[maxn]; int a[maxn]; double p; struct matrix{ double a[2][2]; }; matrix I={ 1,0, 0,1 }; matrix multi(matrix A,matrix B) { matrix C; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ C.a[i][j]=0; for(int k=0;k<2;k++) C.a[i][j]+=A.a[i][k]*B.a[k][j]; } } return C; } double pow(matrix A,int b) { matrix ans = I; if(b<0) return 0; if(b==0) return 1; while(b){ if(b&1) ans=multi(A,ans),b--; b>>=1; A=multi(A,A); } return ans.a[0][0]; } int main() { int n; while(~scanf("%d%lf",&n,&p)){ memset(dp,0,sizeof(dp)); dp[0]=1.0; for(int i=1;i<=n;i++) scanf("%d",a+i); a[0]=0; sort(a,a+n+1); matrix A={p,1-p,1,0}; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]*(1-pow(A,a[i]-a[i-1]-1)); } printf("%.7lf\n",dp[n]); } return 0; }
POJ3744 Scout YYF I (概率DP + 矩阵优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。