(k-1)個のボールを(a-1)回挿入する。挿入した後、ボールの合計がNより大きくなってはいけないので、N-(k-1)(a-1)からa個選ぶパターンを考える。それぞれのパターンで、(1, 2, ...a)番目のボールの内、(2,...a)番目のボールの添字にk-1を加算する。これは全部…

公式解説とか正解コードとかブログとかいっぱい見た dp[i]= i日目に必要なコンピュータを手に入れるまでに必要な最小の金額 というdpテーブルを作ることを考える dp[0] = 0にしておく dp[i] = min(dp[j]+B[i] | B[i] <= ( Σ(0~j)A[k] - dp[j]) ) 後ろを全部…

グラフDPをする dp[i][j] = (i=0 なら、jが所属している連結成分はaのみで出来ていて、それ以外の連結成分はaとbで出来ている i=1なら、jが所属している連結成分はbのみで〜〜〜 i=2なら、jが所属している連結成分はaとbから〜〜〜 今見ているノードがaの時…