【POJ】3744 Scout YYF I
2024-10-14 05:12:54
http://poj.org/problem?id=3744
题意:直线上n个地雷,n<=10,范围在[1, 100000000],每一次有p的概率向前走一步,1-p的概率向前走两步,问安全通过所有地雷的概率(即走到最后一个地雷的后一格)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef double mtx[2][2];
void mul(mtx &a, mtx &b, mtx &c) {
static mtx t;
for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) {
t[i][j]=0;
for(int k=0; k<2; ++k) t[i][j]=t[i][j]+a[i][k]*b[k][j];
}
memcpy(c, t, sizeof t);
}
double P;
bool flag;
void mpow(mtx &t, int n) {
if(n<0) { memset(t, 0, sizeof t); flag=1; return; }
if(flag) return;
static mtx a, x;
a[0][0]=P; a[0][1]=1;
a[1][0]=1-P; a[1][1]=0;
memset(x, 0, sizeof x);
x[0][0]=1; x[1][1]=1;
while(n) {
if(n&1) mul(x, a, x);
mul(a, a, a);
n>>=1;
}
mul(t, x, t);
}
mtx a, b;
int x[15], n;
int main() {
memset(b, 0, sizeof b);
while(~scanf("%d%lf", &n, &P)) {
for(int i=1; i<=n; ++i) scanf("%d", &x[i]);
sort(x+1, x+1+n);
b[0][0]=1-P;
flag=0;
memset(a, 0, sizeof a);
a[0][0]=1;
for(int i=1; i<=n; ++i) mpow(a, x[i]-x[i-1]-2), mul(a, b, a);
a[0][0]=(a[0][0]<0?-a[0][0]:a[0][0]);
printf("%.7f\n", a[0][0]);
}
return 0;
}
对于每一步状态$d[i]$,发现是由$d[i-1]$和$d[i-2]$转移得到的,那么由于事件$i-1$和事件$i-2$互斥,且根据概率的线性性质,得到:
$d[i]=p*d[i-1]+(1-p)*d[i-2]$
可是有地雷怎么办?分段= =然后讨论之= =
发现范围很大怎么办?转移一样上矩阵= =
反正最后得到矩阵积是这个样子的:
$$
\begin{bmatrix}
1 & 0 \\
\end{bmatrix}
\prod_{i=1}^{n}
\left(
\begin{bmatrix}
p & 1 \\
1-p & 0
\end{bmatrix}^{x_i-x_{i-1}-2}
\begin{bmatrix}
1-p & 0 \\
0 & 0
\end{bmatrix} \right)
$$
然后就行了= =
注意$x$数组不是有序的= =需要排一次序.....要不然就wa了一发QAQ还有poj的bits/stdc++不能用是什么鬼 = =
最新文章
- PHPCMS开启伪静态和织梦开启伪静态的优缺点比较
- Qt中使用ActiveX(3篇)
- 有关RAVE报表 - 大富翁论坛20050419
- Dialog类介绍
- CodeForces 131A cAPS lOCK
- GoF--命令设计模式
- Prepared statements(mysqli &; pdo)
- Xcode最最实用快捷键
- java使用Websocket获取HttpSession出现的问题与解决
- Ubuntu 16.04 Vim安装及配置【转】
- 服务器代理+jQuery.ajax实现图片瀑布流
- MongoDB的搭建并配置主从以及读写分离
- 更改MySQL/Postgresql密码
- 网页中Div的打印
- XVFB实现selenium在linux上无界面运行安装篇
- DialogFragment 监听按键事件的方法(onkeydown)
- 基于Cookie的购物车
- jQuery插件Highcharts
- 设置Git远程仓库
- 【转载】TextView源码解析
热门文章
- Genymotion刷入谷歌应用市场以及获取root权限
- 在ubuntu上搭建开发环境1---在windows7的基础上在安装ubuntu(双系统)
- HDU5781 ATM Mechine(DP 期望)
- NBU bplabel命令擦除磁帶數據
- angular入门
- Win7系统怎么开启远程桌面?Win7远程桌面怎么用(转)
- IIS配置php运行环境默认加载的php.ini路径
- 如何解决";";No boot device available(无可用的引导设备)”错误
- SSH框架应用解析
- css学习(2)-- 常见的CSS属性和值