blog主に競プロ問題の解説を載せてますこの広告は、90日以上更新していないブログに表示しています。モンスターyukicoderbitDPの典型問題。bitDPで解く問題は制限がヒントとなるので楽だ。問題N匹のモンスターがいて、モンスターはいいモンスターと悪いモンスターに分けられる。いいモンスターは1度だけ体力を回復してくれるが、悪いモンスターは体力を削っていく。自分の最大体力は最初100で、悪いモンスターを一匹倒すごとに100ずつ最大体力が増えていく。モンスター全部の相手をしたとき、残すことのできる体力の最大値を答える。途中で体力が0となってしまったらそこまでとする。解法モンスターの相手をする順番を全探索するとO(N!)となってしまう。どのモンスターを相手したかをBitmaskにより管理して、相手にしたモンスターの数が少ない順にdpで計算していけばいい。(残しうる体力の最大値)とする。D[i]の正負で条件分けしたくなるが、実は下のような書き方をすれば場合分けをする必要もない。体力が0のときにcontinueするのを忘れない。N)-1]以下同様のことをC++で書いたもの。ビットカウントを自前の関数でやっている。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。