Cafeteria (easy)

解説

この問題は、いわゆる「ナップザック問題」の類題です。以下のような二次元動的計画法（DP）を考えます。

$$dp[i][j] = \text{ i種類目までの料理を見て、合計コストが } j \text{ のときの最大幸福度}$$

ここで、$i$番目の料理の値段を $c_i$、幸福度を $h_i$ とします。

---

DPの遷移

• 料理を選ばない場合：

  $$dp[i+1][j] = \max(dp[i][j], dp[i+1][j])$$

• 料理を選ぶ場合（ただし $j + c_i \leq C$ のとき）：

  $$dp[i+1][j + c_i] = \max(dp[i][j] + h_i, dp[i+1][j + c_i])$$

---

初期化

$$dp[0][0] = 0$$

---

最終的な答え

$$\max_{0 \leq j \leq C} dp[N+1][j]$$

---

計算量

• 時間計算量：$O(NC)$
• 制約条件の範囲内で十分高速に処理可能です。

---

このようにして、問題を効率的に解くことができます。(この解説はCopilotを利用して記述しています。)