HBC230852[HAOI2007]覆盖问题,贪心,二分,分治Cards of Magic题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

Raiden Shogun, the ruler of Inazuma, is playing a new card game invented by her friend Yae Miko. Pixiv ID: 93716380 The player needs to defeat a monster of health point (HP) nnn by using magic cards properly. Specifically, there are three kinds of magic cards: Waterman: Summon the Waterman on the field and the Waterman will stay on the field forever. Each time when you cast a magic card and the Waterman has been on the field, it will reduce the monster's HP by 1. Note that if you cast another Waterman card when the Waterman has already been on the field, nothing will happen except the monster's HP decresing by 1; Fireball: Reduce the monster's HP by 2; Copy: Copy any card casted before this card and receive a copy of the copied card. At the beginning of each turn, the player receives a new card from one of the three kind in equal possibility of 13frac{1}{3}31​. Then the player can choose to cast some magic cards in his hand one by one and the casted cards will take effect respectively. Since there is no limitation for the number of cards in hand, the player can choose to keep cards and do nothing in the turn. The monster will be defeated if its HP becomes nonpositive. Now Raiden Shogun hopes you can calculate the expected number of turns to defeat the monster if she plays optimally to minimize the expected number of turns.

标签： HBC230852[HAOI2007]覆盖问题 贪心 二分 分治Cards of Magic题解