No.951 【本日限定】１枚頼むともう１枚無料！
$ P_i:=i個目のピザの価格
$ D_i:=i個目のピザの美味しさ
$ a_{i,j}:=予算$ i(1\leq i\leq K)円で、$ j$ (0\leq j\leq N-1)番目(0-indexed)までのプレゼントを買う時の美味しさの最大値
とする。
数列$ (P_i) が昇順になるようにピザの順番を並び替えておく。買うピザの番号の数列を$ (q_i)_{1\leq i\leq m}とすると、無料で買うピザの番号は $ i \not\equiv m \bmod 2とするのが最適。従って、漸化式
$ a_{i,j+1}=\max(a_{i,j},D_{j+1}+\max_{1\leq m\leq j}(D_m+a_{i-P_{j+1},m-1}))
がなりたつ。$ b_{i,j}:=\max_{1\leq m\leq j}(D_m+a_{i,m-1})とすると、
$ a_{i,j+1}=\max(a_{i,j},D_{j+1}+b_{i-P_{j+1},j})
となる。$ (b_{i,j}) は各$ a_{i,j}について$ O(1)で更新できるので、$ O(KN)で$ a_{K,N-1}が求まる。