Broken robot
2024-09-05 02:45:17
题意:
要在$nm$的矩阵中从 $(i,j)$ 处移动到第 $n$ 行,每次移动可在不动、左移一格、右移一格、下移一格 4 种选择中等概率随机选一种,但移动不能超出矩阵。求移动次数的期望,最少保留4位小数。
解法:
考虑概率dp
$f(i,j)$ 表示从 $(i,j)$ 移动到第 $n$ 行的期望步数。
这样有
$f(i,j) = \frac{f(i+1,j)}{3} + \frac{f(i,j-1)}{3} + \frac{f(i,j+1)}{3} + \frac{4}{3}, (1<j<m)$
$f(i,1) = \frac{f(i+1,1)}{2} + \frac{f(i,2)}{2} + \frac{3}{2}$
$f(i,m) = \frac{f(i+1,m)}{2} + \frac{f(i,m-1)}{2} + \frac{3}{2}$
$f(n,j) = 0$
注意到 $f(i,j)$ 固定 $i$ 得到一个 nxn 的行列式。
方法一
行列式变形,三对角矩阵
https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
方法二
该 m 递推式是以指数级别收敛的,所以直接迭代30次即可。
最新文章
- MessageFormat用法
- GUI_Delay函数
- 图论(网络流):UVa 1659 - Help Little Laura
- cxf-webservice-在was6服务器上运行
- 【Maven】项目添加Maven类库依赖
- 使用Jenkins来构建Docker容器
- 快速构建Windows 8风格应用5-ListView数据控件
- iOS 开发者旅途中的指南针 - LLDB 调试技术
- 大数据平台搭建-zookeeper集群的搭建
- java对象与Json字符串之间的转化(fastjson)
- 盒子显隐,伪类边框,盒子阴影,2d平面形变
- shell脚本-1
- 原创科幻短篇《VR》
- Zabbix3.x 监控磁盘IO与自定义模板
- 【Mybatis】mybatis使用示例
- 【Python】使用geocoder找出本机IP所在经纬度和城市
- 常用的js 总结
- echarts中关于自定义legend图例文字
- Java IO流经典练习题
- WPF中Image显示本地图片(转)
热门文章
- Jememeter和Loadrunner测试MySQL性能
- web前端面试系列 - 算法( 数组去重 )
- IP分配及网段划分
- 数据库MySQL经典面试题之SQL语句
- teradata培训文档 相关索引
- EasyDarwin开源社区 短视频拍摄项目Github地址
- zoj 2271 Chance to Encounter a Girl <;概率DP>;
- c# winform 根据窗体自动调整控件
- Linux下Redis C++操作的封装
- MYSQL进阶学习笔记十四:MySQL 应用程序优化!(视频序号:进阶_32)