題干：

題目大意：

在一條不滿地雷的路上（無限長），你現在的起點在1處。在N個點處布有地雷，1<=N<=10。地雷點的可能坐標范圍：[1,100000000].

每次前進p的概率前進一步，1-p的概率前進2步。問順利通過這條路的概率。就是不要走到有地雷的地方。

設dp[i]表示到達i點且不踩地雷的概率，如果1號點沒有地雷，則初始值 dp[1]=1.

很容易想到轉移方程： dp[i]=p*dp[i-1]+(1-p)*dp[i-2];

解題報告：

不難發現，對于沒有地雷的一段，可以用map來離散，然后用矩陣快速冪優化轉移。每遇到一個地雷就斷開一次，于是最多進行十次矩陣快速冪就可以解決。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; struct Matrix {double m[2][2]; } unit,empty; map<int,double> dp; Matrix mul(Matrix a,Matrix b) {Matrix c = empty;for(int i = 0; i<2; i++) {for(int j = 0; j<2; j++) {for(int k = 0; k<2; k++) {c.m[i][j] += a.m[i][k]*b.m[k][j];}}} return c; } Matrix qpow(Matrix a,int b) {Matrix c = unit;while(b) {if(b&1) c = mul(c,a);b>>=1;a = mul(a,a);} return c; } int n,d[22]; double p; int main() {unit.m[1][1] = unit.m[0][0] = 1;while(~scanf("%d%lf",&n,&p)) {dp.clear();for(int i = 1; i<=n; i++) scanf("%d",d+i);sort(d+1,d+n+1);int flag = (d[1] != 1);for(int i = 1; i<n; i++) {if(d[i+1] - d[i] == 1) flag = 0;}if(flag == 0) {puts("0.0000000");continue;}Matrix trans,ans;trans.m[0][0]=p;trans.m[0][1] = 1-p;trans.m[1][0] = 1;trans.m[1][1]=0;dp[0] = 0;dp[1] = 1;int last = 1,tar;for(int i = 1; i<=n; i++) {tar = d[i] - 1;ans = qpow(trans,tar-last);dp[tar] = ans.m[0][0]*dp[last] + ans.m[0][1]*dp[last-1];last = tar+2; dp[last] = dp[tar]*(1-p);dp[d[i]]=0;}printf("%.7f\n",dp[tar]*(1-p));}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 3744】Scout YYF I（概率dp，矩阵快速幂优化dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。