2020-04-21から1日間の記事一覧
AtCoder
AtCoder500点
ABC-E
DP
N個からK個を選ぶ設定の問題
ある量を固定して考える
ある量を決めるとGreedy
ナップサックDP
絶対値やminを扱う問題
順列の最適化問題
Greedy
DP状態削減テク:全部分集合でなく個数のみ持つ
最大値や最小値に着目する
最適化テク:解を変形していく(最適性を失わずに)
探索順序を工夫して解く
最大スコア
黄色diff
順列を題材とした問題
非自明な比較関数でソートする
ZabtonDP
最適化問題
探索順序を上手に決めると、普通の DP になる系!!! EDPC の Zubton なんかもそうやね! 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…