首页 > 代码库 > 【poj3744】 Scout YYF I

【poj3744】 Scout YYF I

http://poj.org/problem?id=3744 (题目链接)

题意

  给出n个雷,分别在 a[1]...a[n] ,走一步概率为 p ,走两步概率为 1-p ,一开始在 1 号位置,问安全到达终点的概率。

Solution

  很显然的dp:f[i]=p*f[i-1]+(1-p)*f[i-2]。考虑a[i]位置上有雷,那么安全通过的概率也就是到达f[a[i]+1]的概率为:f[a[i]-1]*(1-p)。

  因为a[i]很大,所以要分段用矩阵快速幂。

细节

  代码能力下降的厉害。。。莫名Wa了的可以去看看Discuss,好坑。。

代码

// poj3744#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define eps 1e-8#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;double tmp[2][2],f[2][2],t[2][2],p;int a[20],n;void power(int k) {	t[0][0]=p,t[0][1]=1,t[1][0]=1-p,t[1][1]=0;	while (k) {		if (k&1) {			for (int i=0;i<=1;i++)				for (int j=0;j<=1;j++) {					tmp[i][j]=0;					for (int k=0;k<=1;k++) tmp[i][j]+=f[i][k]*t[k][j];				}			memcpy(f,tmp,sizeof(f));		}		k>>=1;		for (int i=0;i<=1;i++)			for (int j=0;j<=1;j++) {				tmp[i][j]=0;				for (int k=0;k<=1;k++) tmp[i][j]+=t[i][k]*t[k][j];			}		memcpy(t,tmp,sizeof(t));	}}int main() {	while (scanf("%d%lf",&n,&p)!=EOF) {		for (int i=1;i<=n;i++) scanf("%d",&a[i]);		sort(a+1,a+1+n);a[0]=0;		f[1][1]=1;		for (int i=1;i<=n;i++) {			f[1][0]=f[1][1]*p;			f[0][1]=f[1][0]*p+f[1][1]*(1-p);			f[0][0]=f[0][1]*p+f[1][0]*(1-p);			if (a[i]-a[i-1]==1) {f[1][1]=0;break;}			else if (a[i]-a[i-1]==2) f[1][1]=f[1][1]*(1-p);			else if (a[i]-a[i-1]==3) f[1][1]=f[1][0]*(1-p);			else if (a[i]-a[i-1]==4) f[1][1]=f[0][1]*(1-p);			else power(a[i]-a[i-1]-5),f[1][1]=(1-p)*f[0][0];		}		if (fabs(f[1][1])<eps) puts("0.0000000");		else printf("%.7lf\n",f[1][1]);	}	return 0;}

 

【poj3744】 Scout YYF I