Typical DP Contest - K ターゲット

理解してしまえば簡単に見えるが、理解できるまでに時間がかかった。
class k_target {
public:
    //
    // Longest Increasing Subsequence の応用
    //
    #define L(a) a.first
    #define R(a) a.second
    void solve(void) {
            int N;
            cin>>N;
            vector<pair<int,int>> cs;
            REP(i,N)
            {
                int x,r;
                cin>>x>>r;
                cs.emplace_back(x-r,x+r);
            }
            //
            // ターゲットを考えるには [L,R] の両端を考える必要がある。
            // なんとかして片側だけ考えればよいようにしたい。
            //
            //       [l3               r3]    : 4
            //            [l2       r2]       : 3
            //          [l1      r1]          : 2
            //             [l r]              : 1
            //
            // → R についてソートする
            //   ri>rj (i>j) は保証されるので li < lj (i>j) のとき [li ri] と [lj rj]
            //   はターゲットになる
            // → Longest Increasing Subsequence に帰着
            //
            sort(RANGE(cs), [](const pair<int,int> &a, const pair<int,int> &b)->bool {
                    // strictly に内部にないとダメなので R が同じときは長い方の区間を探索しないようにする
                    //
                    //   [l0   r0] : 2
                    // [l1     r1] : 1
                    //
                    return (R(a)==R(b))? L(a)<L(b):R(a)<R(b);
                });
            const int inf = (1<<30);
            vector<int> dp(N+1,inf); // dp[i] := ターゲットのサイズが i であるときの最小 R 座標
            REP(i, N)
            {
                // -l < -l2 < -l1 < -l3 < ... 逆方向にして LIS を解く
                int l = L(-cs[i]);
                *lower_bound(RANGE(dp), l) = l;
            }
            cout<<lower_bound(RANGE(dp), inf)-dp.begin()<<endl;
    }
};