程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 3774 Scout YYF I （矩陣優化的概率DP）

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;
}