Toyota Programming Contest 2023 Spring Qual A (AtCoder Beginner Contest 288) E - Wish List (500)
$ dp[i][j] で$ i番目までの要素で$ j個売り切れている場合の最小費用とする
これを後ろから考えていくと、その商品を$ j回の内どこで買ってもそれより前の商品の$ jに影響を及ぼさないので$ k (i-j \le k \le i)回の内最小の$ C_kを選ぶことができるようになる
後ろの要素$ iから順に各$ jで以下を考える
$ iは必須の場合
$ dp[i+1][j+1]+a_i+\min_{i-j \le k \le i} c_k が最小値なら更新
必須で無い場合
$ dp[i+1][j+1]+a_i+\min_{i-j \le k \le i} c_k が最小値なら更新
選ばない選択肢もあるので$ dp[i+1][j] が最小値なら更新
各最小値更新が$ \mathcal{O}(\log N) なので全体で$ \mathcal{O}(N^2 \log N)
$ c_iの各区間での最小値を全て事前に求めることで$ \mathcal{O}(N^2)