POJ 3744 Scout YYF I （矩阵相乘+概率DP）-蒲公英云

POJ 3744 Scout YYF I （矩阵相乘+概率DP）

POJ 3744 Scout YYF I （矩阵相乘+概率DP）：http://poj.org/problem?id=3744

题面：

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7254		Accepted: 2118

Description

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy’s base. After overcoming a series difficulties, YYF is now at the start of enemy’s famous “mine road”. This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1- p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the “mine road” safely.

Input

The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

Output

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

Sample Input

Sample Output

0.5000000
0.2500000

题目大意：

一条路上有n个雷，走一步的可能性是p，走两步的可能性是1-p，起点为1，求安全抵达n的概率。

题目分析：

矩阵相乘的题目，

如果k号位有雷，那么安全通过这个雷只可能是在k-1号位选择走两步到k+1号位。因此，可以得到如下结论：在第i个雷的被处理掉的概率就是从a[i-1]+1号位到a[i]号位的概率。于是，可以用1减去就可以求出安全通过第i个雷的概率，最后乘起来即可，但是由于数据很大，所以需要用到矩阵快速幂，类似斐波那契数列，有ans[i]=p*ans[i-1]+(1-p)*ans[i-2]，构造矩阵为：

代码实现：

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
double p;
int a[20];
double b[5][5];
double s[5];
double tmp[5][5];
double temp[5];
double Count(int t)
{
    b[0][0]=p;
    b[0][1]=1-p;
    b[1][0]=1;
    b[1][1]=0;
    s[0]=1;
    s[1]=0;
    while(t!=0)
    {
        if(t%2==1)
        {
            for(int i=0;i<2;i++)
            {
                temp[i]=0;
                for(int j=0;j<2;j++)
                {
                    temp[i]+=b[i][j]*s[j];
                }
            }
            for(int i=0;i<2;i++)
            {
                s[i]=temp[i];
            }
        }
        t/=2;
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                tmp[i][j]=0;
                for(int k=0;k<2;k++)
                {
                    tmp[i][j]+=b[i][k]*b[k][j];
                }
            }
        }
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                b[i][j]=tmp[i][j];
            }
        }
    }
    return s[0];
}
int main()
{
    double ans=0;
    while(scanf("%d%lf",&n,&p)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        a[0]=0;
        sort(a,a+n+1);
        ans=1;
        for(int i=0;i<n;i++)
        {
            ans=ans*(1-Count(a[i+1]-a[i]-1));
        }
        printf("%.7lf\n",ans);
    }
    return 0;
}