Typical DP Contest K - ターゲット

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_target

解法

それぞれの円の左端と右端のpairである (x + r, x - r) を昇順ソートする．
そのあと，-(x - r) についての最長増加部分列（ (x - r) のまま考えるなら，最長減少部分列．右から左の向き）を求めると，それが答えになる．

strictly に内部に含んでいるという条件だが，(x + r, -(x - r)) でなく (x + r, x - r) でまずソートしているので，仮に x + r が同じ円が2つあっても，境界が重なる円に影響しないような順番で LIS に値が代入されるので問題ない．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

constexpr int INF = 1e9 + 1;

int main() {
    int N;
    cin >> N;
    vector<pii> circle(N);
    for(int i = 0; i < N; ++i) {
        int x, r;
        cin >> x >> r;
        circle[i] = make_pair(x + r, x - r);
    }
    sort(circle.begin(), circle.end());

    vector<int> LIS(N, INF);
    for(int i = 0; i < N; ++i) {
        *lower_bound(LIS.begin(), LIS.end(), -circle[i].second) = -circle[i].second;
    }
    int res = find(LIS.begin(), LIS.end(), INF) - LIS.begin();

    cout << res << endl;
}

感想

自力で解けなかった．そんなに苦手なタイプでないDPなので解けるべきだった．
セグツリとか使うなら嫌だなあと思ったけどこれは頭がいいですね…．