当前位置: 代码迷 >> 综合 >> poj 3744 Scout YYF I 概率dp+矩阵乘法
  详细解决方案

poj 3744 Scout YYF I 概率dp+矩阵乘法

热度:26   发布时间:2024-01-19 05:42:55.0

分析:

dis(k,v1,v2)函数求到当前位置概率为v1,到当前位置之前一步的概率为v2,前进k步到达位置的概率,然后矩阵加速。

代码:

//poj 3744
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
int pos[12];
double p,mat[4][4];
double ans[4][4];void mul1()
{double c[4][4];c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0;for(int i=0;i<2;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k)c[i][j]+=ans[i][k]*mat[k][j];for(int i=0;i<2;++i)for(int j=0;j<2;++j)ans[i][j]=c[i][j];
}void mul2()
{double c[4][4];c[0][1]=c[1][0]=c[0][0]=c[1][1]=0.0;for(int i=0;i<2;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k)c[i][j]+=mat[i][k]*mat[k][j];for(int i=0;i<2;++i)for(int j=0;j<2;++j)mat[i][j]=c[i][j];
}double dis(int len,double val,double val1)
{mat[1][0]=1.0;mat[0][1]=1-p;mat[0][0]=p;mat[1][1]=0;ans[1][0]=ans[0][1]=0;ans[0][0]=ans[1][1]=1.0;while(len){if(len&1) mul1();mul2();len>>=1;}		return ans[0][0]*val+ans[0][1]*val1;
}int main()
{int n;while(scanf("%d%lf",&n,&p)==2){pos[0]=0;for(int i=1;i<=n;++i)scanf("%d",&pos[i]);		sort(pos+1,pos+1+n);double ans=1,a1=1,a0=0;for(int i=1;i<=n;++i){if(pos[i]==pos[i-1]) continue;ans=ans-dis(pos[i]-pos[i-1]-1,a1,0);a1=ans;}printf("%.7lf\n",ans);}return 0;	
}