poj 3774 Scout YYF I （矩阵优化的概率DP） - c++编程基础

题意： 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]

因为直接暴力求解超时，构造矩阵

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             #include
             
               #define INF 0x7fffffff #define SUP 0x80000000 #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long LL; const int N=100007; struct Matrix{ double mat[2][2]; }; Matrix mul(Matrix a,Matrix b) //矩阵乘法 { Matrix ret; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { ret.mat[i][j]=0; for(int k=0;k<2;k++) ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; } } return ret; } Matrix qpow(Matrix a,int n) //矩阵快速幂 { Matrix ret; mem(ret.mat,0); for(int i=0;i<2;i++) ret.mat[i][i]=1; Matrix tmp=a; while(n) { if(n&1) ret=mul(ret,tmp); n>>=1; tmp=mul(tmp,tmp); } return ret; } int a[20]; int main() { int n; double p; while(scanf("%d%lf",&n,&p)==2) { for(int i=1;i<=n;i++) scanf("%d",a+i); sort(a+1,a+1+n); double ans=1; Matrix fir,tmp; fir.mat[0][0]=p; fir.mat[0][1]=1-p; fir.mat[1][0]=1; fir.mat[1][1]=0; tmp=qpow(fir,a[1]-1); ans*=(1-tmp.mat[0][0]); for(int i=2;i<=n;i++) { if(a[i]==a[i-1]) continue; tmp=qpow(fir,a[i]-a[i-1]-1); ans*=(1-tmp.mat[0][0]); } printf("%.7f\n",ans); } return 0; }