题目链接：http://poj.org/problem?id=3744 题意解析：这题大意是给定一条路， 有n个地雷，从一开始以p的概率走一步，以1-p的概率走俩步，问你安全通过的概率是多少。 难点：因为地雷的范围为1~100000000，用不了一般的dp数组求解，所以我们要用矩阵连乘来优化； ( p) (1-p)–(1) -----------* (1) (0)-----(0) 代码：
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; struct node { double dp[3][3]; }; int n; double p; int a[101]; node work(node p,node q) { node r; memset(r.dp,0,sizeof(r.dp)); for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { for(int k=0; k<3; k++) { r.dp[i][j]+=p.dp[i][k]*q.dp[k][j]; } } } return r; } double pow(int n) { node c,ans; memset(c.dp,0,sizeof(c.dp)); ans.dp[1][1]=p; ans.dp[1][2]=1-p; ans.dp[2][1]=1.0; ans.dp[2][2]=0.0; c.dp[1][1]=1.0; c.dp[1][2]=0.0; while(n) { if(n&1) c=work(c,ans); ans=work(ans,ans); n>>=1; } return c.dp[1][1]; } int main() { while(scanf("%d %lf",&n,&p)!=EOF) { memset(a,0,sizeof(a)); for(int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); double res=1.0; for(int i=1; i<=n; i++) { res*=(1.0-pow(a[i]-a[i-1]-1)); } printf("%.7lf\n",res); } return 0; }