ZabtonDP
AOJ
JAG
DP
探索順序を工夫して解く
ナップサックDP
DEGwerさんの数え上げテクニック集の例題
数え上げ問題
極大なものを考える
条件の言い換え
部分和
ある量を固定して考える
累積和テク:左右両端からの累積和や累積結果を前処理
AOJ-ICPC500点
JAG夏合宿
AOJ-ICPC
累積和
前処理
典型要素を詰め合わせた教育的問題
【問題集】DPのステップアップ
累積和テク:累積和や累積結果を前処理しておく
累積和の亜種
ZabtonDP
これ面白い!! 問題へのリンク editorials 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選ぶ方法のうち、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 選んだ数の総和は 以下である 選んだ数の総…
AtCoder
AtCoder500点
ABC-E
DP
N個からK個を選ぶ設定の問題
ある量を固定して考える
ある量を決めるとGreedy
ナップサックDP
絶対値やminを扱う問題
順列の最適化問題
Greedy
DP状態削減テク:全部分集合でなく個数のみ持つ
最大値や最小値に着目する
最適化テク:解を変形していく(最適性を失わずに)
探索順序を工夫して解く
最大スコア
黄色diff
順列を題材とした問題
非自明な比較関数でソートする
ZabtonDP
最適化問題
探索順序を上手に決めると、普通の DP になる系!!! EDPC の Zubton なんかもそうやね! 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…