Scout YYF I POJ - 3744(概率dp)

Description

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy‘s base. After overcoming a series difficulties, YYF is now at the start of enemy‘s famous "mine road". This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely.

Input

The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

Output

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

Sample Input

1 0.5
2
2 0.5
2 4

Sample Output

0.5000000
0.2500000

一条路上一共有n个地雷,每次从 i 位置有 p 的概率走向 i+1 位置,有 1-p 的概率走向 i+2 位置,问在这条路上走不被炸死的概率是多大。用dp[i] = x 表示走到第 i 个位置的概率,那么dp[i] = p * dp[i-1] + (1-p) * dp[i-2].但是 i 的范围在 1e8 内,所以不能直接遍历。一开始想错了,以为第 x 位置的地雷只会对后面两个位置产生影响,这种情况是 p = 0.5的特殊情况下的。假设地雷的位置是x1, x2 可以把 1->x1 之间不踩到地雷和 x1+1 -> x2 之间不踩到地雷看成两个独立事件,然后最后讲每次(1-dp[地雷])的概率相乘就可以了。然后接下来就是对从 1->x 过程求 dp[x] 概率了,这个过程可以通过矩阵快速幂来加速。

  1 /*
  2           .
  3          ‘;;;;;.
  4         ‘!;;;;;;!;`
  5        ‘!;|&#@|;;;;!:
  6       `;;!&####@|;;;;!:
  7      .;;;!&@$$%|!;;;;;;!‘.`:::::‘.
  8      ‘!;;;;;;;;[email protected]###&|;;|%!;!$|;;;;|&&;.
  9      :!;;;;[email protected]&%|;;;;;;;;;|!::!!:::;!$%;!$%`    ‘!%&#########@$!:.
 10      ;!;;!!;;;;;|$$&@##$;;;::‘‘‘‘‘::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$;
 11      ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%`
 12     `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&;
 13     :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@|
 14     ;|::;;;;;;;;;;;;|&&$|;;[email protected]&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.
 15    `!!;;;;;;;!!!!;;;;;[email protected]@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.
 16 %&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##!
 17 !%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&:
 18 ‘:|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%.
 19  [email protected]|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&‘
 20   .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@:
 21   .%$;;;;;;;;;;;;;;;;;;|[email protected]&|;;;;;;;;;;;;;;;;;;;;%@%.
 22     !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;
 23      `%$!;;;;;;;;;;;[email protected]|;;;;;;;;;;;;;;;;;;;;;;;;!%[email protected]#@|.
 24        .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%[email protected]#|.
 25            ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.
 26            |##$|!;;;;;;::‘‘:;;;;;;;;;;;;;!%[email protected]#@;
 27           ;@&|;;;;;;;::‘‘‘‘‘‘:;;;;;;;|$&@###@|`
 28         .%##@|;;;;:::‘‘‘‘‘‘‘‘‘‘::;!%&##$‘
 29       `$##@[email protected]@&|!!;;;:‘‘‘‘‘::::;;;;;|&#%.
 30     ;&@##&$%!;;;;;;::‘‘‘‘‘‘‘‘::;!|%[email protected]#@&@@:
 31      .%@&$$|;;;;;;;;;;:‘‘‘‘:‘‘‘‘::;;;%@#@@#%.
 32     :@##@###@$$$$$|;;:‘‘‘‘:;;!!;;;;;;!$#@@#$;`
 33      `%@$$|;;;;;;;;:‘‘‘‘‘‘‘::;;;;|%$$|!!&###&‘
 34      |##&%!;;;;;::‘‘‘‘‘‘‘‘‘‘‘‘::;;;;;;;[email protected]&:`!‘
 35     :;[email protected]$|;;;;;;;::‘‘‘‘‘‘‘‘‘‘‘:;;;;;;;;!%&@$:                 [email protected]#$‘
 36       |##@@&%;;;;;::‘‘‘‘‘‘‘‘‘:;;;;;;;!%&@#@$%:              ‘%%!%&;
 37       |&%!;;;;;;;%$!:‘‘‘‘‘‘‘:|%!;;;;;;;;|&@%||`            ‘%$|!%&;
 38       |@%!;;!!;;;||;:‘‘‘‘‘‘:;%$!;;;;!%%%&#&%$&:           .|%;:!&%`
 39       [email protected]&%;;;;;;;||;;;:‘‘::;;%$!;;;;;;;|&@%;!$;          `%&%!!$&:
 40       ‘$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##;         !$!;:!$&:
 41        |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%‘      `%$|%%;|&$‘
 42         |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&;  .:%&$!;;;:[email protected]!
 43         `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@!
 44         !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%`
 45        ‘%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%[email protected]@|‘
 46        .!%%&%‘`|$;       :|$#%|@#&;%#%.
 47 */
 48 #include <map>
 49 #include <set>
 50 #include <list>
 51 #include <ctime>
 52 #include <cmath>
 53 #include <stack>
 54 #include <queue>
 55 #include <string>
 56 #include <vector>
 57 #include <cstdio>
 58 #include <bitset>
 59 #include <cstdlib>
 60 #include <cstring>
 61 #include <iostream>
 62 #include <algorithm>
 63 #define  lowbit(x)  x & (-x)
 64 #define  mes(a, b)  memset(a, b, sizeof a)
 65 #define  fi         first
 66 #define  se         second
 67 #define  pii        pair<int, int>
 68 #define  INOPEN     freopen("in.txt", "r", stdin)
 69 #define  OUTOPEN    freopen("out.txt", "w", stdout)
 70
 71 typedef unsigned long long int ull;
 72 typedef long long int ll;
 73 const int    maxn = 1e5 + 10;
 74 const int    maxm = 1e5 + 10;
 75 const int    mod  = 1e9 + 7;
 76 const ll     INF  = 1e18 + 100;
 77 const int    inf  = 0x3f3f3f3f;
 78 const double pi   = acos(-1.0);
 79 const double eps  = 1e-8;
 80 using namespace std;
 81
 82 int n, m;
 83 int cas, tol, T;
 84
 85 struct Mat {
 86     double mat[5][5];
 87     void init() {
 88         for(int i=1; i<=2; i++) {
 89             for(int j=1; j<=2; j++) {
 90                 mat[i][j] = 0.0;
 91             }
 92         }
 93     }
 94 };
 95 int a[15];
 96
 97 Mat mmul(Mat A, Mat B) {
 98     Mat ans;
 99     ans.init();
100     for(int i=1; i<=2; i++) {
101         for(int j=1; j<=2; j++) {
102             for(int k=1; k<=2; k++) {
103                 ans.mat[i][j] += A.mat[i][k] * B.mat[k][j];
104             }
105         }
106     }
107     return ans;
108 }
109
110 Mat mpow(Mat A, int b) {
111     Mat ans;
112     ans.init();
113     for(int i=1; i<=2; i++)
114         ans.mat[i][i] = 1.0;
115     while(b) {
116         if(b & 1)
117             ans = mmul(ans, A);
118         A = mmul(A, A);
119         b >>= 1;
120     }
121     return ans;
122 }
123
124 int main() {
125     double p, q;
126     while(~scanf("%d%lf", &n, &p)) {
127         mes(a, 0);
128         q = 1.0 - p;
129         int flag = 0;
130         for(int i=1; i<=n; i++) {
131             scanf("%d", &a[i]);
132             if(a[i] == 1) {
133                 flag = 1;
134             }
135         }
136         if(flag) {
137             printf("0.0000000\n");
138             continue;
139         }
140         a[n+1] = 0;
141         n++;
142         sort(a+1, a+1+n);
143         double ans = 1.0;
144         Mat A;
145         for(int i=2; i<=n; i++) {
146             if(a[i] == a[i-1])    continue;
147             int tmp = a[i] - a[i-1] + 1;
148             if(tmp == 2) {
149                 ans *= 0.0;
150             } else {
151                 A.mat[1][1] = p;
152                 A.mat[1][2] = q;
153                 A.mat[2][1] = 1.0;
154                 A.mat[2][2] = 0.0;
155                 A = mpow(A, tmp-2);
156 //                for(int i=1; i<=2; i++) {
157 //                    for(int j=1; j<=2; j++) {
158 //                        printf("%f%c", A.mat[i][j], j==2 ? ‘\n‘ : ‘ ‘);
159 //                    }
160 //                }
161                 ans *= (1 - A.mat[1][1]);
162             }
163         }
164         printf("%.7f\n", ans);
165     }
166     return 0;
167 }

原文地址:https://www.cnblogs.com/H-Riven/p/10080844.html

时间: 12-07

Scout YYF I POJ - 3744(概率dp)的相关文章

poj 3744 概率dp+矩阵快速幂

题意:在一条布满地雷的路上,你现在的起点在1处.在N个点处布有地雷,1<=N<=10.地雷点的坐标范围:[1,100000000]. 每次前进p的概率前进一步,1-p的概率前进1-p步.问顺利通过这条路的概率.就是不要走到有地雷的地方. 设dp[i]表示到达i点的概率,则 初始值 dp[1]=1. 很容易想到转移方程: dp[i]=p*dp[i-1]+(1-p)*dp[i-2]; 但是由于坐标的范围很大,直接这样求是不行的,而且当中的某些点还存在地雷. N个有地雷的点的坐标为 x[1],x[2

poj 2151 概率dp

//poj 2151 概率dp 1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm" 5 using namespace std; 6 double dp[33][33]; 7 int M, T, N; //problem, team, least 8 double p[1010][33]; 9 int mai

poj 2096 (概率DP)

http://poj.org/problem?id=2096 概率DP: 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 double dp[1003][1003]; 5 int main() 6 { 7 int n,s,i,j; 8 cin>>n>>s; 9 for (i=n;i>=0;i--) 10 { 11 for (j=s;j>=0;j--) 12 { 13

poj 3071 概率dp

//分析:明显的树形关系,题目描述的是一棵高 n + 1的完全二叉树,则 dp[树层号][team号](规定最底层为 0 层,层数朝节点的方向依次递增),推一下就好了 //稍微需要想一下的是比赛双方的选取,下面给出两种方法 //#1 枚举起点划分team区间 1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm"

poj 3744 Scout YYF I(概率dp,矩阵优化)

Scout YYF I Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5020   Accepted: 1355 Description YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties,

POJ 3744 Scout YYF I (概率DP+矩阵快速幂)

题意:小明要从1走过一段直线雷区,给定n个地雷的坐标,他走一步的概率是p,两步的概率为1-p,问你他能安全通过雷区的概率. 析:很明显这是一个概率DP,用d(i)表示到达 i 时他安全的概率,那么d[i] = p * d[i-1] + (1-p) * d[i-2];这个状态转移方程很好理解, 就是说要想到达 i 要么从第 i-1 走一步,要么从 i-2 走两步,最后加起来,然后问题来了,这个数可能达到 1E8,那么时间空间复杂度都受不了, 观察这个状态转移方程,是不是很像Fibnacci数列,所

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

分析: 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]

【概率DP】POJ 3744 Scout YYF I

通道 题意:每次走一步的概率是p,走两步的概率是1-p,然后有n个点上有地雷.问YYF走过雷区的概率是多少 思路: dp[i]=p*dp[i-1]+(1-p)dp[i-2] 转移矩阵:   ans[i]    | p ,1-p   |    ans[i-1]            =|             | * ans[i-1]   | 1 , 0     |   ans[i-2] 代码:

POJ 3744 Scout YYF I 矩阵快速幂

Scout YYF I Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4452   Accepted: 1159 Description YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties,

POJ 3744 Scout YYF I

概率$dp$,矩阵优化. 设$dp[i]$为到位置$i$存活的概率,那么如果位置$i$是雷区,$dp[i]=0$,否则$dp[i]=p*dp[i-1]+(1-p)*dp[i-2]$.求出最后一个雷区位置的后一个位置的$dp$值就是答案.长度较大,可以矩阵优化加速一下.输出%$lf$不让过,%$f$过了. #pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<c