SRM610 Div2 Hard MiningGoldEasy

問題

TopCoder Statistics - Problem Statement

解法

xとyを独立に考える。

任意の動き方に対してx,yのそれぞれに対して座標の変化が起こらないような区間を考える。 すると関数 f(x) = \sum_{i=0}^{n} {|x-a[i]|} は f(a[i]) のうちのどれかを最小値としてとるような凸関数であるので、 event_i、event_jに含まれるような座標の組み合わせに対する動き方のみ考えればよい。

よって座標圧縮してDPすればよい。

コード

証明が本質？