poj3744(矩阵连乘优化概率dp)

题目链接：http://poj.org/problem?id=3744
题意解析：这题大意是给定一条路， 有n个地雷，从一开始以p的概率走一步，以1-p的概率走俩步，问你安全通过的概率是多少。
难点：因为地雷的范围为1~100000000，用不了一般的dp数组求解，所以我们要用矩阵连乘来优化；
( p) (1-p)–(1)
-----------*
(1) (0)-----(0)
代码：

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct node
{
    double dp[3][3];
};
int n;
double p;
int a[101];
node work(node p,node q)
{
    node r;
    memset(r.dp,0,sizeof(r.dp));
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            for(int k=0; k<3; k++)
            {
                r.dp[i][j]+=p.dp[i][k]*q.dp[k][j];
            }
        }
    }
    return r;
}
double pow(int n)
{
    node c,ans;
    memset(c.dp,0,sizeof(c.dp));
    ans.dp[1][1]=p;
    ans.dp[1][2]=1-p;
    ans.dp[2][1]=1.0;
    ans.dp[2][2]=0.0;
    c.dp[1][1]=1.0;
    c.dp[1][2]=0.0;
    while(n)
    {
        if(n&1)
            c=work(c,ans);
        ans=work(ans,ans);
        n>>=1;
    }
    return c.dp[1][1];
}
int main()
{
    while(scanf("%d %lf",&n,&p)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        double res=1.0;
        for(int i=1; i<=n; i++)
        {
            res*=(1.0-pow(a[i]-a[i-1]-1));
        }
        printf("%.7lfn",res);
    }
    return 0;

}

最后

以上就是飞快早晨为你收集整理的poj3744(矩阵连乘优化概率dp)的全部内容，希望文章能够帮你解决poj3744(矩阵连乘优化概率dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。