http://arc070.contest.atcoder.jp/tasks/arc070_c
関数dpとかいうやつ。僕のいうところの「愚直に値を持つ」dpと同じです。
愚直にx座標すべて持ってみることを考えて、実は本当に持つ必要があるものは少なくて、更新も簡単にできる、みたいな感じです。
|x-c|を足すと、x=cで傾きが2変わることを失念してWA生やしました。
あとsetで最後の要素を消すのはS.erase(--S.end())です。
dpというとこのパターンと、考察して状態量を減らすパターンがあるのかな?前者はなんとかなりそうだけど、後者は一般的な解き方がなくて難しそう。
int N; multiset<ll> L, R; int A[MAX_N], B[MAX_N]; void solve() { cin >> N; rep(i, 0, N) cin >> A[i] >> B[i]; ll a = A[0], b = A[0]; L.insert(A[0]); R.insert(A[0]); ll ans = 0; rep(i, 1, N) { a -= B[i] - A[i]; b += B[i - 1] - A[i - 1]; ll l = *L.rbegin(), r = *R.begin(); if(a <= A[i] && A[i] <= b) { L.insert(A[i] - (a - l)); R.insert(A[i] - (b - r)); a = A[i]; b = A[i]; } else if(A[i] < a) { ans += abs(A[i] - a); L.insert(A[i] - (a - l)); L.insert(A[i] - (a - l)); ll le = *L.rbegin() + (a - l); L.erase(--L.end()); R.insert(le - (b - r)); a = *L.rbegin() + (a - l); b = le; } else { ans += abs(A[i] - b); R.insert(A[i] - (b - r)); R.insert(A[i] - (b - r)); ll rb = *R.begin() + (b - r); R.erase(R.begin()); L.insert(rb - (a - l)); a = rb; b = *R.begin() + (b - r); } } cout << ans << "\n"; }