HBC234881[SCOI2010]股票交易,动态规划,单调队列单调栈,数据结构Checkpoints题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Gildong 正在设计一个包含编号从111到 nnn的nnn个关卡组成的游戏，玩家从第一关开始并且需要按照关卡编号升序通过每一关，当玩家通过第nnn关时获得胜利， 每一个关卡中至多有一个检查点，并且第一关一定存在一个检查点，在游戏开始的时候，只有第一关的检查点是被激活的，其他所有检查点都是未激活状态，当玩家到达一个拥有检查点的关卡时，该检查点会被激活， 对于

Gildong 正在设计一个包含编号从 111 到 nnn 的 nnn个关卡组成的游戏。玩家从第一关开始并且需要按照关卡编号升序通过每一关。当玩家通过第 nnn 关时获得胜利。 每一个关卡中至多有一个检查点，并且第一关一定存在一个检查点。在游戏开始的时候，只有第一关的检查点是被激活的，其他所有检查点都是未激活状态。当玩家到达一个拥有检查点的关卡时，该检查点会被激活。 对于每一个关卡，玩家可能会成功通过或者失败。如果玩家通过了第 iii 个关卡，他就可以移动到第 i+1i+1i+1 个关卡。如果他们失败了，他们会回到最近激活的检查点处，并需要重新通过检查点以后的关卡。 例如，假设 n=4n=4n=4 并且检查点位于第一个和第三个关卡。玩家从第一关开始，如果他失败，那么他就需要重新尝试第一关因为第一关的检查点是最近激活的检查点。如果他通过了第一关并且移动到第二关，但是他在第二关失败，那么他会重新回到第一关。如果他通过了第一关和第二关，那么他就会到达第三关并且第三关的检查点会被激活。现在无论他在第三关失败，还是通过第三关后在第四关失败，他都会被送回第三关。如果他通过了第三关和第四关，他就获得了胜利。 Gildong 计划将关卡设置为相同的难度。他想要你设计一个至多有 2000 关的方案，使得获胜所需要通过关卡的期望次数恰好为 kkk。 对于一个玩家而言，通过每一关的概率恰好为 12frac{1}{2}21​。

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC234881[SCOI2010]股票交易 动态规划 单调队列单调栈 数据结构Checkpoints题解