読者です 読者をやめる 読者になる 読者になる

AOJ 2244 Dungeon Quest II

n(<=1000)回攻撃される.i回目の攻撃で体力がDi減る.始めの体力はHsで体力の最大値はHmax(<=1000).体力が0以下になると死.
回復薬がP(<=12)個ある.それぞれの攻撃の前に好きな個数だけ回復薬を使える.i個目の回復薬を使うと体力がPi回復する(Hmaxを超えるとHmaxになる).使ったらなくなる.最後まで生きれるならYES,無理ならNOをoutputせよ.

dp[i][j]="i回攻撃受けた時点での回復薬使用状況(bit)がjの時の体力のmax"を持てば良さそう.それぞれの状態からどの回復薬のsubsetを使うか、を考えるとO(n*P*3^P)となり死亡.
よく考えると、回復薬aとbを使いたいときはaを使った状態を(その回の更新時に使う)dpに放り込んでおけばok.ということはdp[i]=回復薬状況iのときのmaxHPをトポロジカル順序で(0から回せば良い)更新していけば良いことがわかる.

ポイント:bit状況からsubsetを増やす,みたいな操作があり,subsetの要素の増やす順によって値が変わらないなら,トポロジカル順に増やせば良い.