Typical DP Contest K - ターゲット
問題
n個の円があり、それぞれの中心はx軸上にある。
i番目の円の中心はxi, 半径はriである。
円の列C1, C2, ..., Cnは、円Ci+1がCiの真に内部に入っているときにターゲットであると言う。作れるターゲットの最大のサイズを求めよ。
制約条件
n≦100000
方針
円を右端が大きい順にならべる。
で、左端の最長増加部分列を求めればよい。
n年前の自分はbinary indexed treeを使いよくわからないことをしたようだ。
ソースコード
const int MX = 100010; int bit[MX]; inline int sum(int i){ int res = 0; for(; i; i -= i & -i) res = max(res, bit[i]); return res; } inline void add(int i, int x){ for(; i < MX; i += i & -i) bit[i] = max(bit[i], x); } int n; vector<pi> in; vi xs; int main(){ cin >> n; rep(i, n){ int x, r; cin >> x >> r; in.pb(mp(-x - r, x - r)); xs.pb(x - r); } sort(all(xs)); sort(all(in)); for(int i = 0; i < n; ){ vi v; for(int j = i; j < n && in[i].first == in[j].first; j++){ int x = lower_bound(all(xs), in[j].second) - xs.begin(); v.pb(sum(x) + 1); } rep(j, v.size()){ int x = lower_bound(all(xs), in[i++].second) - xs.begin() + 1; add(x, v[j]); } } cout << sum(n + 5) << endl; return 0; }
残り解説書いてない問題はG, L, M, N, S.
解いたの大分前だしほとんど忘れている…