程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 3744 Scout YYF I (概率DP+矩陣快速冪)

POJ 3744 Scout YYF I (概率DP+矩陣快速冪)

編輯：關於C++

題目地址：POJ 3744

一個線性概率DP遞推式。dp[i]=p*dp[i-1]+(1-p)*dp[i-2]。但是i的值太大。所以可以分成n次，每一次中間過程的純遞推過程用矩陣快速冪來優化。只要想到矩陣快速冪就挺簡單了。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=100000000;
const int INF=0x3f3f3f3f;
const double eqs=1e-8;
int a[20];
double dp[20];
struct Matrix
{
    double ma[3][3];
}init, res;
Matrix Mult(Matrix f1, Matrix f2)
{
    int i, j, k;
    Matrix tmp;
    memset(tmp.ma,0,sizeof(tmp.ma));
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            tmp.ma[i][j]=0;
            for(k=0;k<2;k++){
                tmp.ma[i][j]+=f1.ma[i][k]*f2.ma[k][j];
            }
        }
    }
    return tmp;
}
Matrix Pow(Matrix x, int k)
{
    Matrix tmp;
    int i, j;
    for(i=0;i<2;i++) for(j=0;j<2;j++) tmp.ma[i][j]=(i==j);
    while(k){
        if(k&1) tmp=Mult(tmp,x);
        x=Mult(x,x);
        k>>=1;
    }
    return tmp;
}
int main()
{
    int n, i, flag, k;
    double p, p1, p2;
    while(scanf("%d%lf",&n,&p)!=EOF){
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        a[0]=0;
        sort(a,a+n+1);
        flag=0;
        for(i=1;i<=n;i++){
            if(a[i]==a[i-1]+1||a[i]==1){
                flag=1;
                break;
            }
        }
        if(flag){
            printf("0.0000000\n");
            continue ;
        }
        init.ma[0][0]=p;init.ma[0][1]=1-p;
        init.ma[1][0]=1;init.ma[1][1]=0;
        p1=1;
        for(i=1;i<=n;i++){
            if(a[i]-a[i-1]==2){
                p1=p1*(1-p);
            }
            else{
                p2=p1*p;
                k=a[i]-a[i-1]-3;
                res=Pow(init,k);
                p1=(p2*res.ma[0][0]+p1*res.ma[0][1])*(1-p);
                //printf("k--%d\n",k);
            }
            //printf("%.7f\n",p1);
        }
        printf("%.7f\n",p1);
    }
    return 0;
}