Scout YYF I POJ - 3744【矩阵乘法优化求概率】
2024-09-03 03:40:45
题意:
一条路上有 $n$ 个地雷,YYF 从位置 $1$ 出发,走一步的概率为 $p$,走两步的概率是 $(1-p)$。求 YYF 能顺利通过这条路的概率。
数据范围: $1\leq n \leq 10$,$0.25\leq p\leq 0.75$,输入的 $n$ 个位置的范围:$[1,1e8]$
分析:
从前往后推,状态转移方程:$dp[i]=dp[i-1]*p+dp[i-2]*(1-p)$,其中 $dp[1]=1$,有地雷的位置 $dp[i]=0$。如果直接算,必然超时,可以用矩阵快速幂分段优化。
坑点:输入的 $n$ 个位置不一定有序。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; ]; double p; struct matrix { ][]; void clc() { ;i<;i++) ;j<;j++) mat[i][j]=; } void eye() { ;i<=;i++) mat[i][i]=; } matrix operator *(const matrix b)const { matrix res; res.clc(); ;i<=;i++) { ;k<=;k++) { ;j<=;j++) res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]); } } return res; } }; matrix mpow(matrix a,int b) { matrix res; res.clc(); res.eye(); while(b) { ) res=res*a; a=a*a; b>>=; } return res; } void init(matrix &a) { a.clc(); a.mat[][]=; } void init2(matrix &b) { b.clc(); b.mat[][]=p; b.mat[][]=; b.mat[][]=-p; } int main() { int n,x,last; while(scanf("%d%lf",&n,&p)!=EOF) { ;i<=n;i++) scanf("%d",&a[i]); sort(a+,a++n); matrix A,B; init(A); init2(B); ; last=; ;i<=n;i++) { A=A*mpow(B,a[i]-last);//cout<<"A="<<A.mat[1][2]<<endl; A.mat[][]=; last=a[]; } A=A*B; printf(][]); } ; }
最新文章
- 排序算法----调用库函数qsort进行快速排序
- bzoj3388(神奇的解法)
- maven添加本地jar包
- python对象
- <;<;Design Patterns>;>; Gang of Four
- 模拟实现ORM实例
- Github教程(2)
- C#中的lock关键字
- XtraBackup原理3
- How to Analyze Java Thread Dumps--reference
- Java文件File操作一:文件的创建和删除
- kbhit()
- 用SpriteBuilder简化";耕牛遍地走";的动画效果(二)
- Java:全局变量(成员变量)与局部变量
- [转]Spring通过@Value注解注入属性的几种方式
- 【English】主语从句的引导词是如何选择?
- HDU 2147 kiki&#39;s game(博弈经典题)
- Linux各种类型压缩包解压缩方法
- Leetcode--680. Valid Palindrome II(easy)
- cordova开发ios炸鸡