POJ 3744 Scout YYF I（矩阵快速幂优化+概率dp）-白红宇

POJ 3744 Scout YYF I（矩阵快速幂优化+概率dp）

阅读量：4971 次

发布时间：2019-06-12

本文共 1721 字，大约阅读时间需要 5 分钟。

题意：

现在有个屌丝要穿越一个雷区，雷分布在一条直线上，但是分布的范围很大，现在这个屌丝从1出发，p的概率往前走1步，1-p的概率往前走2步，求最后顺利通过雷区的概率。

思路：

首先很容易能得到一个递推式：$dp[i]=p*dp[i-1]+(1-p)*dp[i-2]$。但是直接递推肯定不行，然后我们发现这个很容易构造出矩阵来，但是这样还是太慢。

接下来讲一下如何优化，对于第i个雷，它的坐标为x[i]，那么那顺利通过它的话，只能在x[i]-1的位置走2步。

观察上图，可以发现每次起点就相当于是雷后面的一个格子，这样的话我们就可以分块处理（有多少雷就分多少块），先计算出起点到雷的概率y，那么1-y就是顺利通过这块的概率。最后乘法原理乘起来即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 #include
              
               11 using namespace std;12 typedef long long ll;13 const int INF = 0x3f3f3f3f;14 const int maxn=100000+10;15 16 int n;17 double p, ans;18 int x[15];19 20 struct Matrix21 {22 double mat[2][2];23 Matrix()24 {25 for(int i=0;i<2;i++)26 for(int j=0;j<2;j++)27 mat[i][j]=0;28 }29 Matrix operator* (const Matrix& b) const30 {31 Matrix c;32 for(int i=0;i<2;i++)33 for(int j=0;j<2;j++)34 for(int k=0;k<2;k++)35 c.mat[i][j]+=mat[i][k]*b.mat[k][j];36 return c;37 }38 }base;39 40 Matrix q_pow(Matrix base, int n)41 {42 Matrix res;43 res.mat[0][0]=res.mat[1][1]=1;44 while(n)45 {46 if(n&1) res=res*base;47 base=base*base;48 n>>=1;49 }50 return res;51 }52 53 int main()54 {55 //freopen("in.txt","r",stdin);56 while(~scanf("%d%lf",&n,&p))57 {58 for(int i=1;i<=n;i++) scanf("%d",&x[i]);59 sort(x+1,x+n+1);60 base.mat[0][0]=p;61 base.mat[0][1]=1-p;62 base.mat[1][0]=1;63 base.mat[1][1]=0;64 ans=1;65 Matrix tmp=q_pow(base, x[1]-1);66 ans*=(1-tmp.mat[0][0]);67 for(int i=2;i<=n;i++)68 {69 if(x[i]==x[i-1]) continue;70 tmp=q_pow(base, x[i]-x[i-1]-1);71 ans*=(1-tmp.mat[0][0]);72 }73 printf("%.7f\n",ans);74 }75 return 0;76 }

转载于:https://www.cnblogs.com/zyb993963526/p/7448507.html

你可能感兴趣的文章