poj 3744 Scout YYF I(递推求期望)

题意：给出n个坑，一个人可能以p的概率一步一步地走，或者以1-p的概率跳过前面一步，问这个人安全通过的概率

解法：

递推式：

对于每个坑，我们可以这么定义一个数组: d[i]代表它安全落在位置i的概率，在这个1到max(a[i])的范围中，只有那些坑是不安全的，答案只需求出所有不掉入坑的概率的连乘即可

矩阵：

由于数字范围巨大，需要对递推式进行矩阵连乘加速

| p 1-p |    | d[i]   |   | d[i+1] |

| 1  0  |  * | d[i-1] |  =| d[i]   |

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef double ll;

const int MOD=1e9+7;

int tn;

struct Matrix

{

    double m[111][111];

    Matrix()

    {

        memset(m,0,sizeof(m));

    }

    friend Matrix operator*(Matrix a,Matrix b)

    {

        Matrix res;

        double x;

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

        {

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

            {

                x=0;

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

                {

                    x=(x+(ll)a.m[i][k]*b.m[k][j]);

                }

                res.m[i][j]=x;

            }

        }

        return res;

    }

    friend Matrix operator+(Matrix a,Matrix b)

    {

        Matrix res;

        ll x;

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

        {

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

            {

                res.m[i][j]=(a.m[i][j]+b.m[i][j]);

            }

        }

        return res;

    }

    friend Matrix operator^(Matrix a,int b)

    {

        Matrix ans;

        for(int i=0;i<tn;i++) ans.m[i][i]=1;

        for(int i=b; i; i>>=1,a=a*a)

            if(i&1)ans=ans*a;

        return ans;

    }

} T,F;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void init(double p){

    for(int i=0;i<tn;i++) F.m[i][i]=1;

    T.m[0][0]=p;T.m[0][1]=1-p;

    T.m[1][0]=1;

}

int main()

{

     tn=2;

     int n,a[20]={0};

     double p;

     while(cin>>n>>p){

        init(p);

        for(int i=1;i<=n;i++) cin>>a[i];

        sort(a+1,a+1+n);

        double ans=1;

        if(a[1]==1){

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

            continue;

        }

        Matrix tmp;

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

            if(a[i]==a[i-1]){

                continue;

            }

            if(a[i]-a[i-1]>2){

               tmp=T^(a[i]-a[i-1]-2);

               ans*=(tmp.m[0][0])*(1-p);    //算出a[i]-1的概率，然后跳过a[i]的概率

            }else{

               tmp=T^(a[i]-a[i-1]-1);

               ans*=1-(tmp.m[0][0]);      //反向求出不落入a[i]的概率

            }

        }

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

     }

     return 0;

}

巴特西

poj 3744 Scout YYF I(递推求期望)

poj 3744 Scout YYF I(递推求期望)

最新文章

热门文章