Atcoder水色精進記録
ABC216
F - Max Sum Counting
https://atcoder.jp/contests/abc216/tasks/abc216_f
アルゴリズム・データ構造
DP
考察
条件の左辺が選択したAのmax
→sortすると簡単にできそう。
sortしたAを小さい順に考えると、そのインデックス以下のBしか考えなくてよくなる。
条件のうへんが選択したBの合計値
→累積和が使える？→途中のインデックスを使わないことがあるので累積和は使えない。
一つずつ使う使わないを考える？
→全探索は最大2**5000
→DPを検討
保持しておかないといけない情報は？
→それまでの組み合わせの数、現在までの使用するBの合計MAX5000*5000
→合計値が大きすぎるため削れる部分を考える。
→Bの合計値が現在の最大のAを超える場合は不要(AのMAXは5000)
→現在までの合計の状態は0-5000でOK
計算量
Aのソート NlogN
dp N*N
提出
感想
DPについて慣れてきた。