Codeforces Round #688(Div 2) D. Checkpoints
思路
第一步，先推导1,0,0,……，0，就是1后面跟了n-1个0的时候
所需要的期望步数
封闭式推导
\(f_n\)代表从n关开始直接通关需要的步数的期望
n为1的情况，即就只有一个1
\(f_1=\cfrac{1}{2} \times 1+\cfrac{1}{2} \times (f_1+1)\)
整理得\(f_1=2\)
第一关时，你有一半的概率通关，有一半的概率回到自身重新开始
n为2的情况，1,0
\(f_1=\cfrac{1}{2} \times 1+\cfrac{1}{2} \times (f_2+1)\)
\(f_2=\cfrac{1}{2} \times 1+\cfrac{1}{2} \times (f_1+1)\)
整理得\(f_1=6\)
第一关时，你有一半的概率到达第二关，有一半的概率回到自身重新开始
第二关时，你有一半的概率通关，有一半的概率回到第一关重新开始
这样我们就可以进行归纳总结
把每个式子化简一下
\(f_1=\cfrac{1}{2} f_1+\cfrac{1}{2} f_2+1\)
\(f_2=\cfrac{1}{2} f_1+\cfrac{1}{2} f_3+1\)
\(f_3=\cfrac{1}{2} f_1+\cfrac{1}{2} f_4+1\)
……
\(f_i=\cfrac{1}{2} f_1+\cfrac{1}{2} f_{i+1}+1\)
……
\(f_n=\cfrac{1}{2} f_1+1\)
然后自己整理一下，就是两个等比数列的和
就得到了\(f_1\)的封闭式
对于任意情况的n时，\(f_1=2^{n+1}-2\)
思路推进
推导出1,……，0,0的期望公式之后，我们如果再后面继续添加1,0,……，0这样一个序列
那么他的期望是直接相加的，因为他是一个复活点（检查点），跟你前面的序列一点关系都没有
所以你无论怎么增加都是一个2的倍数，这样也就得到奇数的时候是无解的
代码实现
最新文章
- iOS开发之CocoaPods的安装与使用
- POJ2488A Knight's Journey[DFS]
- ASP.NET中EVAL用法大全
- Javascript&Jquery获取浏览器和屏幕各种高度宽度方法总结及运用
- C# 显式创建线程 or 使用线程池线程--new Thread() or ThreadPool.QueueUserWorkItem()
- svnserve: E000098: 不能绑定服务器套接字: 地址已在使用
- java基础知识点---equal，==，hashcode
- Linux时间子系统之五：低分辨率定时器的原理和实现
- ROS学习笔记(一) ： 入门之基本概念
- EXCEL 将网络图片地址插入为锁定的图片单元格宏
- python 搭建redis集群
- python字符串的基本用法
- mac环境下配置nginx
- win10 开机背景图
- 剑指offer：数组中出现次数超过一半的数
- mvc area出现“找到多个与名为“Home”的控制器匹配的类型”错误的解决方法
- vim配置之目录结构
- (转)Python进阶：函数式编程(高阶函数，map,reduce,filter,sorted,返回函数,匿名函数,偏函数)
- Subversion、TortoiseSVN、Ankhsvn+VS使用
- （1.4）DML增强功能-Output