洛谷3750 [六省联考2017]分手是祝愿

$$ \text{首先可以证明,把原局面从到大小一个一个关所经历的步数一定最少} \\ \left( \text{每次必定选择编号最大的没有关闭的灯} \right) \text{所以先求出来这个步数。} \\ \text{如果这个步数不超过}k\text{,那么这个步数就是答案。} \\ \text{否则设}f\left( i \right) \text{表示还剩}i\text{步的时候,随机选择一个开关是转移到还剩}i-\text{1步的期望步数。} \\ f\left( i \right) =\frac{i}{n}\left( \text{选中了一个正确的开关} \right) +\left( 1-\frac{i}{n} \right) \left( f\left( i \right) +f\left( i+1 \right) +1 \right) \left( \text{选中了一个错误的开关,那么步数}+1 \right) \\ \text{显然}f\left( n \right) =\text{1,此时随便选一个开关都会让步数少}1. \\ \text{整理得}f\left( i \right) =1+\frac{n-i}{i}\left( f\left( i+1 \right) +1 \right) \\ \text{计算出}f\left( k+1 \right) \text{到}f\left( n \right) \text{的答案累加起来,加上}k\text{即可。} \\ $

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据