ABC219_D – Strange Lunchbox

問題

D - Strange Lunchbox

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44909874 - Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

3回目くらいで解けた。

2回くらいACできず、解説をみた。
今回、ACできた。

3次元のdpで解いた。
dp配列は以下のように定義する。
$$dp[i][j][k]: i番目の弁当まで見た時、たこ焼きj個、たい焼きk個になる最小の弁当の個数$$

j,kの最大値はX,Yとし、X,Y以上のものはX,Yだと思って計算すると、X,Yの場所は「たこ焼きX個以上たい焼きY個以上になる最小の弁当の個数」とすることができる。