https://atcoder.jp/contests/abc216/tasks/abc216_f
前提知識
解説
https://atcoder.jp/contests/abc216/submissions/25449760
DPが分かっていることは前提なので勉強してきてほしい。
何から始めるのか
手がつかない場合は問題の弱点を探るのが良い。
今回は条件のうち、maxの上限が5000である部分が弱点となりうる部分である。
maxの上限が5000であるということはBの総和の上限も5000まで考えればいいことになる。
この条件は考察するうえでとても有用な条件であるように見える。
まあ、ここまではいいとして、ここからちょっと思考の飛躍が必要となる。
条件のmaxの値は選択された値の中での最大値によって決まり、
「それより小さい数についてはどのように選択されても変化しない」
といえる。
ここがとても重要な部分で、この「どのように選択されても変化しない」という部分にDPの同一視が適用できそうである。
さて、小さい数について、細かな状態は無視したいので、配列をまずはソートすることにする。
AとBを1つのグループにまとめてAでソートしておく。
max, sumや部分集合の選択方法に順番は影響しないので、ソートしても答えは変化しない。
この状態でDPを考える。
DP定義
dp[i][Btot] := i番目まで選択が確定していて、かつ、「i番目を選択していて」、かつ、選択した要素のBの総和がBtotである組合せ
このDPを更新していくことを考える。
これを貰うDPで実装していくことを考えると、
dp[to][Btot]の更新はto未満である全てのcuに対してdp[cu][Btot - B[to-1]]の総和
が更新ルールとなる。
これをそのまま実装するとO(N2 Bmax)になるので間に合わない。
更新時に利用している値は、toを1から順番に計算していることを考えるとdp[to未満の全て][とある値]の総和を取得していることになる。
これは事前に計算することができる。
よって、
tot[x] := dp[これまで][x]の総和
と定義して、dp[to][any]の更新が終わった直後に、totにその値を入れることで、
dp[to][any]を更新→tot[x]を更新→更にそれを使ってdp[to+1][any]を更新→…みたいな感じに高速に計算ができる。
この辺は累積和を使った更新最適化と捉えることもできる。
https://blog.hamayanhamayan.com/entry/2017/03/20/234711
答えを取得する
これでdp[i][Btot]について考えると、maxの値はA[i-1]になっているので、BtotがA[i-1]以下であるものが条件を満たすものになる。
なので、全てのdpの要素dp[i][Btot]についてBtot≦A[i-1]である組合せの総和を取れば答えになる。
int N; int A[5010], B[5010]; pair<int, int> AB[5010]; mint dp[5010][5010]; mint tot[5010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) cin >> B[i]; rep(i, 0, N) AB[i] = { A[i], B[i] }; sort(AB, AB + N); dp[0][0] = 1; tot[0] = 1; rep(to, 1, N + 1) { rep(Btot, 0, 5010) if (AB[to - 1].second <= Btot) dp[to][Btot] = tot[Btot - AB[to - 1].second]; rep(Btot, 0, 5010) tot[Btot] += dp[to][Btot]; } mint ans = 0; rep(to, 1, N + 1) rep(Btot, 0, AB[to - 1].first + 1) ans += dp[to][Btot]; cout << ans << endl; }