POJ 3744 【矩阵快速幂优化 概率DP】

搞懂了什么是矩阵快速幂优化....

这道题的重点不是DP.

/*

题意：

小明要走某条路，按照个人兴致，向前走一步的概率是p，向前跳两步的概率是1-p，但是地上有地雷，给了地雷的x坐标，（一维），求小明安全到达最后的概率。

思路：

把路分成好多段，小明安全走完每一段的概率乘起来就是答案。

dp[i]=p*dp[i-1]+(1-p)*dp[i-2];

参考fib数列构造矩阵进行快速幂。

注意初始化的时候，起点概率看作1，起点减一也就是有地雷的地方概率看作0。//屌丝一开始在这里没搞明白。

*/

#include<stdio.h>

#include<math.h>

#include<algorithm>

#include<string.h>

using namespace std;

struct mat

{

    double m[][];

};

mat from;

double ans[];

mat mul(mat a,mat b)

{

    mat c;

    double tmp=;

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            tmp=;

            for(int k=;k<;k++)

            {

                tmp+=a.m[i][k]*b.m[k][j];

            }

            c.m[i][j]=tmp;

        }

    }

    return c;

}

int jilu[];

mat calpow(int n)

{

    mat tmp=from;

    mat ans;

    memset(ans.m,,sizeof(ans.m));

    ans.m[][]=;

    ans.m[][]=;

    while(n)

    {

        if(n&)

        {

            ans=mul(ans,tmp);

        }

        tmp=mul(tmp,tmp);

        n/=;

    }

    return ans;

}

double solve(int n)

{

    mat ttt;

    ttt=calpow(n);

    return -ttt.m[][];

}

int main()

{

    int n;

    double p;

    while(scanf("%d%lf",&n,&p)!=EOF)

    {

        from.m[][]=p;

        from.m[][]=-p;

        from.m[][]=;

        from.m[][]=;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&jilu[i]);

        }

        sort(jilu+,jilu++n);

        ans[]=solve(jilu[]-);

        for(int i=;i<=n;i++)

        {

            ans[i]=solve(jilu[i]-jilu[i-]-);//这里为什么减一以后要注意了

        }

        double rel=;

        for(int i=;i<=n;i++)

        {

            rel*=ans[i];

        }

        printf("%.7lf\n",rel);

    }

}