POJ 3744 Scout YYF I——概率dp+分段矩阵快速幂

POJ 3744 Scout YYF I——概率dp+分段矩阵快速幂

题意：

给出n个障碍的坐标，规定玩家一开始在坐标1处，每次有概率p前进1个单位，有概率1-p前进两个单位，问越过所有障碍的概率

思路：

定义dp[i]为到达坐标i的概率，那么dp[i] = c[i] * (dp[i-1]+dp[i-2])，c[i]表示坐标i是否有障碍

这个式子可以用分段矩阵快速幂优化，首先将坐标分成n段：

0~a[1]

a[1]+1~a[2]

......

a[n-1]+1~a[n]

对于每一段要求的是（1-达到a[i]）的概率，然后把这n段的结果相乘就是答案

#include #include #include #include using namespace std;struct Matrix { double m[2][2]; } matrix;Matrix mul(Matrix m1, Matrix m2) { Matrix ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { ans.m[i][j] = 0; for (int k = 0; k < 2; k++) ans.m[i][j] += m1.m[i][k] * m2.m[k][j]; } } return ans;}Matrix mpow(Matrix m, int n) { Matrix ans; ans.m[0][0] = 1, ans.m[0][1] = 0; ans.m[1][0] = 0, ans.m[1][1] = 1; while (n) { if (n & 1) ans = mul(ans, m); m = mul(m, m); n >>= 1; } return ans;}int main() { int n, a[20]; double p; while (~scanf("%d%lf", &n, &p)) { a[0] = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+1+n); n = unique(a+1, a+1+n)-(a+1); matrix.m[0][0] = p, matrix.m[0][1] = 1-p; matrix.m[1][0] = 1, matrix.m[1][1] = 0; double ans = 1; for (int i = 1; i <= n; i++) { Matrix res = mpow(matrix, a[i]-a[i-1]-1); ans *= (1 - res.m[0][0]); } printf("%.7f\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。