Typical DP Contest - K ターゲット
K: ターゲット - Typical DP Contest | AtCoder
- 理解してしまえば簡単に見えるが、理解できるまでに時間がかかった。
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; } };