ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店

提出コード
満点を取るには、ほぼO(1)でクエリにこたえていかないといけません。
そこで、
ans[i][j] = i番目の品物を使わずにj個選ぶ方法
とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。
まず初めに、重複組み合わせを求めます。

動的計画法における重複組み合わせの式変形について - ツバサの備忘録

こちらの記事に考え方を載せました。結果としては、
dp[i][j]=dp[i][j−1]+dp[i−1][j]−dp[i−1][j−ai−1]
となります。
ここまでは通常通り求めてしまいます。
これを、”戻す”形にします(つまり、i+1を参照することでi番目を求めるような形にします)。
といっても式変形をするだけです。iが絡む部分全てに1を足し、両辺を整えて、 "dp[i][j] =" という形に直すと、
dp[i][j] = dp[i+1][j] - dp[i+1][j-1] + dp[i][j-ai-1]
となります。
さて、ここで品物の順番は何も関係がない、ということが重要になってきます。
つまりは、今は
dp[i][j] = i番目までの品物からj個選ぶ方法の数
となっていますが、i番目の品物とn番目の品物を入れ替えるだけで、任意の番号の品物を考慮しないような選び方の個数を求めることができます。
なので、i+1を全体での選び方、iを除外したい番号に置き換えると、
ans[i][j] = i番目を選ばずに、j個を選ぶ方法の個数
を求めることができ、
ans[i][j] = dp[n][j] - dp[n][j-1] + ans[i][j-ai-1]
となります。
あとは、iとjをループして二回目のDPをすれば、それぞれのクエリにO(1)で答えることができるようになります。