POJ3744 Scout YYF I 概率DP+矩阵快速幂

http://poj.org/problem?id=3744

题意：一条路，起点为1，有概率p走一步，概率1-p跳过一格（不走中间格的走两步），有n个点不能走，问到达终点（即最后一个坏点后）不踩坏点的概率为多少。坏点的坐标范围 [1，100000000]

 

概率dp的算是入门题…其实写起来和以前的矩阵似乎并没有什么区别呢…状态其实还挺好想的。

坏点sort一下；然后把每一个坏点后一格走到一个坏点前一格的概率乘到答案上，再乘一个1-p跳到坏点后，循环即可。

 

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//using namespace std;
const int maxn=10010;
const double eps=1e-8;
const int modn=45989;
int n;double p,ans;
int b[20]={};
double c[2]={};
struct mat{
    double e[5][5];
    mat(){memset(e,0,sizeof(e));}
};mat a;
void yu(){
    memset(b,0,sizeof(b));
    a.e[1][2]=1.0;
    a.e[2][1]=1.0-p;
    a.e[2][2]=p;
    ans=1;
}
mat Mul(mat x,mat y){
    mat z;
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                z.e[i][j]+=x.e[i][k]*y.e[k][j];
            }
        }
    }
    return z;
}
mat Pow(mat x,int k){
    mat z;
    z.e[1][1]=1;z.e[2][2]=1;
    while(k){
        if(k&1){
            z=Mul(x,z);
        }
        k/=2;
        x=Mul(x,x);
    }
    return z;
}
int main(){
    while(~scanf("%d%lf",&n,&p)){
        yu();
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        std::sort(b+1,b+1+n);
        b[0]=0;
        int f=0;
        for(int i=1;i<=n;i++){
            if(b[i]==b[i-1]+1){
                printf("%.7f
",0.0);
                f=1;
                break;
            }
        }if(f) continue;
        c[0]=1.0,c[1]=p;
        for(int i=1;i<=n;i++){
            if(b[i]-b[i-1]==2);
            else if(b[i]-b[i-1]==3){
                ans*=p;
            }else{
                mat z=Pow(a,b[i]-b[i-1]-3);
                ans*=c[0]*z.e[2][1]+c[1]*z.e[2][2];
            }
            ans*=(1.0-p);
        }
        printf("%.7f
",ans+eps);
    }
    return 0;
}