備忘録代わりに精進記録を載せていくつもりです。クエリにこたえていかないといけません。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番目を求めるような形にします)。いっても式変形をするだけです。dp[i][j-ai-1]となります。ここで品物の順番は何も関係がない、ということが重要になってきます。i番目までの品物からj個選ぶ方法の数となっていますが、i番目の品物とn番目の品物を入れ替えるだけで、任意の番号の品物を考慮しないような選び方の個数を求めることができます。ans[i][j-ai-1]となります。答えることができるようになります。橋の下をN隻の船がくぐります。(1)注目記事はてなブログをはじめよう!emtubasaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。