【ZOJ 3200】Police and Thief
2024-10-12 00:00:53
ZOJ 3200
首先我写了个高斯消元，但是消出来了一些奇怪的东西，我就放弃了。。。
然后只好考虑dp：\(dp[i][j][k]\)表示走到了第i步，到了\((j,k)\)这个节点的概率。
那么答案就是边上节点在所有的步数走到的概率加起来第一次超过\(p%\)的地方。
然后转移的时候枚举现在要走到哪一个方向，走到\((j',k')\)，就可以转移到\(dp[i+1][j'][k']\)。
然后一共需要走的步数是看对于当前这一步所有的节点所能到达的概率是不是都是0（为了浮点误差，我们需要把=0改成小于EPS）
如果全等于0，那么下一步也没有去转移的必要了。
最后把所有的边上的答案加起来。为了不爆空间，滚动数组，只把边上的和记录下来即可。
还为了不tle，循环展开，直接转移到\((j+1,k)(j-1,k)(j,k+1)(j,k-1)\)即可。
最新文章
- 手把手写php框架中三大“自动功能”
- Fedora 21 install chrome
- mysql有回滚，php没有回滚的说法
- o2o的一些看法
- BubbleSort - 实用委托
- javascript 中 offsetWidth,clientWidth;offsetHeight,clientHeight的区别
- C++中引用用于结构
- 如果Centos没有桌面，怎么修改IP地址
- WebService学习------小实例开发（号码归属地查询）
- 『这是一篇干货blog』
- vue cli 3.x 项目部署到 github pages
- Debian 无线网络切换问题解决方案
- java框架之SpringCloud(2)-Rest微服务案例
- Spring中使用@Value读取porperties文件中的属性值方法总结及注意事项
- pycharm开发django项目 static报404解决方法
- Azure PowerShell (15) 批量导出Azure ASM/ARM VM信息
- SharePoint Online 设置网站集
- flexbox常用布局左右固定，中间自适应
- net core 2.0学习笔记（一）：开发运行环境搭建 (转)
- kubernetes traefik multiple namespaces