Poisonous Full Course: Renewal

解説

前提：「コスト$C_k$を支払う」を「満足度に$-C_k$が加算される」と読み替えます。

以下のようなDPで解くことができます：

$$dp[\text{時刻}][\text{レストラン or 病院}][\text{現在罹っている毒}] = \text{幸福度の最大値}$$

遷移は以下が考えられます：

• レストランに居て毒$k$入りの料理を食べる場合：
  • 毒$k$に罹っている場合は、現在の幸福度に$A_i$を足し、$\text{[現在罹っている毒]}$から$k$を取り除いて次の時刻の病院に移動する。
  • 毒$k$に罹っていない場合は、現在の幸福度に$A_i$を足し、$\text{[現在罹っている毒]}$に$k$を追加して次の時刻に移動する。
• レストランに居て、解毒剤$k$入りの料理を食べる場合は、$\text{[現在罹っている毒]}$から$k$を取り除いて次の時刻に移動する。
• 病院に居る場合：
  • 毒を治療せずに次の時刻のレストランに移動する。
  • それぞれの毒$k$に対して：
    • 幸福度から$C_k$を引いたうえで$\text{[現在罹っている毒]}$から$k$を取り除き、次の時刻に移動する。

計算量は$O(NK2^k)$です。$[\text{現在罹っている毒}]$はbitで管理するとよいでしょう（bitDP）。

実装例（Ruby、726ms）

余談：もともと$K \leq 10$でしたが、Rubyで通らなかったので8まで縮めました。YJITをください