No.027 C

スペシャルチケットの手持ち枚数は取得できるトッピングの種類の上限を示しているだけで, 他には関係ない. スペシャルチケットの手持ち枚数が取得するトッピングの数と同じ場合はすべてのトッピングの入手時に1枚ずつスペシャルチケットを混ぜればいいし, 取得するトッピングの数が少なければ余りのスペシャルチケットを適当なトッピング取得時に混ぜればいい.

あとは典型的 DP で, $i$ 種類目までのトッピングを見たときに $j$ 枚のチケットを使って $k$ 種類のトッピングを手に入れたときの最大幸福を $C(i,j,k)$ として,

$$C(i,j,k) = \max(C(i-1,j,k), C(i-1,j-h_i,k-1) + h_i)$$

で更新していけばいい. $\max_{k \leq \min(X, N)} C(N, *, k)$ が答えである.

なお, $C$ をすべてメモリに置いておくと MLE の可能性があるので $i$ ごとに使い回す. また最大値は int をわずかに超えるので uint か long を使う.