Cafeteria (hard)

解説

次のようなDPを考えます。

• $dp[ i 番目までの料理だけで頼む][頼んだ料理の総和 j 円] = (そのような料理の頼み方は可能か?)$

このDPの推移は次の通りです。ただし、$OR(a,b,c) = a \lor b \lor c$ を表しています。

• $dp[i][j] = OR(dp[i-1][j],dp[i][j-c_i],dp[i][j- 2 \times c_i],dp[i][j- 3 \times c_i],...)$

答えは $dp[N][C] = True$ ならYes,そうでなければNoです。このDPの推移は $i,j$ の二重ループで求めることができます。時間計算量は $O(NC)$ です。