テク:|x|=max(-x,x)
Codeforces
DP
区間分割型ナップサックDP
区間
DP状態:state
負値が本質的に効く問題
絶対値やminを扱う問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP高速化
DP高速化:直前との比較のみでよい
DP状態:長さの総和
数列
二値パラメータ問題
テク:|x|=max(-x,x)
DP状態:ビット
最大スコア
マルチテストケース問題
ナップサックDP
区間分割の仕方を走査する問題
最適化問題
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！ 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
AtCoder
AtCoder500点
ABC-E
緑色diff
マンハッタン距離
二次元平面上のN点の問題
解空間:O(N^2)通りの選択肢
絶対値やminを扱う問題
テク:45度回す
そのまま覚えたい典型問題
テク:2点や2区間の配置関係を考える
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
テク:|x|=max(-x,x)
解空間:O(N^2)個のペア
これ！！！！！HUPC 2019 day2 セットで出したやつや！！！ 問題へのリンク 問題概要 二次元平面上に 個の点 がある。 これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。 制約 考えたこと 2 点の位置関係としては、以下の 2 パターン…
