博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 3744 Scout YYF I 矩阵快速幂
阅读量:6374 次
发布时间:2019-06-23

本文共 3784 字,大约阅读时间需要 12 分钟。

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, 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.522 0.52 4

Sample Output

0.50000000.2500000

Source

, Simon
 
题目大意:给你N个地雷mine[N](均在x轴上)以及一个概率p(0.25 <= p <= 0.75) ,规定起始坐标为1。以x轴正方向为正向,p的概率正向移动一个单位,(1-p)的概率正向移动两位,问你有多少的概率使得不踩到任意一个地雷上。
 
题目分析:由递推公式易知走到第n个点的概率为F(n) = p * F(n - 1) + (1 - p) * F(n - 2)。
为此我们可以构造这样一个矩阵A =  |       p        1  |,可以得到 | F(n - 1)  F(n - 2) | *  |       p        1  |     =   | F(n)    F(n - 1) |。
                                               | (1 - p)   0  |                                            | (1 - p)   0  |
那么F(n)即为 A ^ n。规定A^0 = E(单位矩阵)。
假设第一个地雷坐标为i, 第二个地雷坐标为j。那么从起点开始踩到第i个地雷的概率为F(i - 1), 那么不踩到 i 的概率为1 - F(i - 1)。因为不踩到 i ,所以接下来必定从第 i + 1 开始走,那么在不踩到 i 的前提下踩到到 j 的概率为(1 - F(i - 1)) * F(j - i - 1), 同样的既不踩到 i 又不踩到 j 的概率即(1 - F(i - 1)) * (1 - F(j - i - 1))。
所以最终答案即(1 - F(mine[1] - 1)) * (1 - F(mine[2] - 1) * ... * (1 - F(mine[n] - 1))。
需要注意的是有两种必死的情况:起始点出现地雷或者出现两个地雷相连。
 
代码如下:
#include 
#include
#define REP(i, n) for(int i = 0; i < n; ++i)#define FF(i, n) for(int i = 1; i <= n; ++i)using namespace std;const int O = 2;int N;struct Matrix{ typedef double type; type mat[O][O]; Matrix operator * (const Matrix &t) const{ Matrix tmp; REP(i, N) REP(j, N){ tmp.mat[i][j] = 0; REP(k, N){ tmp.mat[i][j] = (tmp.mat[i][j] + mat[i][k] * t.mat[k][j]); } } return tmp; } Matrix operator + (const Matrix &t) const{ Matrix tmp; REP(i, N) REP(j, N){ tmp.mat[i][j] = (mat[i][j] + t.mat[i][j]); } return tmp; } Matrix operator - (const Matrix &t) const{ Matrix tmp; REP(i, N) REP(j, N){ tmp.mat[i][j] = (mat[i][j] - t.mat[i][j]); } return tmp; }};Matrix E, A;Matrix pow(Matrix a, int k){ Matrix res = E, tmp = a; while(k){ if(k & 1) res = res * tmp; tmp = tmp * tmp; k >>= 1; } return res;}int work(){ int n, mine[11], flag; double p, ans; N = O; mine[0] = 0; REP(i, N) REP(j, N) E.mat[i][j] = (i == j); while(~scanf("%d%lf", &n, &p)){ FF(i, n) scanf("%d", &mine[i]); sort(mine + 1, mine + n + 1); flag = 0; FF(i, n){ if(mine[i] - mine[i - 1] == 1) flag = 1; } if(mine[0] == 1 || flag){ printf("%.7f\n", 0); continue; } A.mat[0][0] = p; A.mat[0][1] = 1; A.mat[1][0] = 1 - p; A.mat[1][1] = 0; ans = 1; FF(i, n){ if(mine[i] == mine[i - 1]) continue; ans *= 1 - pow(A, mine[i] - mine[i - 1] - 1).mat[0][0]; } printf("%.7f\n", ans); } return 0;}int main(){ return work();}
POJ 3744

 

转载于:https://www.cnblogs.com/ac-luna/p/3754864.html

你可能感兴趣的文章
git 忽略文件
查看>>
HTTP、HTTP2.0、HTTPS、SPDY
查看>>
正向代理和反向代理
查看>>
IOS设计模式的六大设计原则之迪米特法则(LOD,Law Of Demeter)
查看>>
c# 第27节 结构、枚举
查看>>
day35——memcache常用方法
查看>>
为什么实体类要实现序列化
查看>>
JVM的重排序
查看>>
某个时间为星期几
查看>>
01背包解题模板
查看>>
antd table 点击行触发radio 或 checkbox
查看>>
利用Adaboost提高分类性能
查看>>
tensorflow之损失函数
查看>>
CENTOS6.2系统日志rsyslog替换默认的日志服务syslog 转载自http://www.phpboy.net/linux/648.html...
查看>>
css3 炫酷下拉菜单
查看>>
前端存取cookie
查看>>
linux c笔记
查看>>
第四次作业
查看>>
angular 5的新特性
查看>>
tcp中设置连接超时
查看>>