程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3744 Scout YYF I（矩陣優化概率）

poj 3744 Scout YYF I（矩陣優化概率）

編輯：C++入門知識

poj 3744 Scout YYF I（矩陣優化概率）

有n個雷，某人的起始位置在1，每次走一步的概率為p,走兩步的概率是1-p,給出n個雷的位置，問最後成功走出雷區的概率。

放在高中應該是很簡單的分步乘法求概率。即把每一個雷都沒踩到的概率求出來，最後n個相乘就是順利通過的概率。對於輸入的n個位置進行分段1~num[1],num[1]+1~num[2]......每一段都只有一個雷num[i]，每一段內踩不到雷的概率就是1-踩到num[i]雷的概率。

設dp[i]表示踩到第i個雷的概率，那麼dp[i] = p*dp[i-1] + (1-p)*dp[i-2]，因為i較大，可以用矩陣相乘進行優化。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;

struct matrix
{
    double mat[2][2];
    void init()
    {
        mat[0][0] = mat[1][1] = 1;
        mat[0][1] = mat[1][0] = 0;
    }
}a,b,res;

int num[15];
int n;
double p;

matrix mul(matrix x, matrix y)
{
    matrix t;
    memset(t.mat,0,sizeof(t.mat));
    for(int i = 0; i < 2; i++)
    {
        for(int k = 0; k < 2; k++)
        {
            if(x.mat[i][k] == 0) continue;
            for(int j = 0; j < 2; j++)
            {
                t.mat[i][j] += x.mat[i][k]*y.mat[k][j];
            }
        }
    }
    return t;
}

matrix pow(matrix a, int n)
{
    matrix t;
    t.init();
    while(n)
    {
        if(n&1)
            t = mul(t,a);
        n >>= 1;
        a = mul(a,a);
    }
    return t;
}

int main()
{
    while(~scanf(%d %lf,&n,&p))
    {
        a.mat[0][0] = p;
        a.mat[0][1] = 1-p;
        a.mat[1][0] = 1;
        a.mat[1][1] = 0;
        memset(b.mat,0,sizeof(b.mat));
        b.mat[0][0] = 1;
        b.mat[1][0] = 0;

        for(int i = 1; i <= n; i++)
            scanf(%d,&num[i]);
        sort(num+1,num+1+n);

        double ans;
        res = pow(a,num[1]-1);
        res = mul(res,b);
        ans = 1 - res.mat[0][0];

        for(int i = 2; i <= n; i++)
        {
            res = pow(a,num[i]-num[i-1]-1);
            res = mul(res,b);
            ans *= (1-res.mat[0][0]);
        }
        printf(%.7f
,ans);
    }
    return 0;

}