poj 3774 Scout YYF I （矩阵优化的概率DP）

思路：

将整个过程划分成阶段处理：

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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#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;
}

poj 3774 Scout YYF I （矩阵优化的概率DP）

原文：http://blog.csdn.net/code_or_code/article/details/44596483