Typical DP Contest K - ターゲット
http://tdpc.contest.atcoder.jp/tasks/tdpc_target
問題
半径ri, 中心(xi, 0)のN個の円が与えられる。この中からどの2円をとっても片方がもう片方の内部に厳密に含まれるようにいくつかの円を選ぶとき、選べる円の最大数を求めよ。
解法
円cとx軸上の2交点を小さい順にLc, Rcとすると円iが円jの内部に含まれるためにはLj < Li かつ Ri < Rj となることが必要十分条件である。よってLで円をソートし、最長減少部分列を求めれば答えが出る。
感想
自力で解けず。円の位置関係の式をこねくりまわして全然わからんとなっていた。いや確かにDPは典型だけどもねきみ
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable int INF = 1 << 29; void main() { auto N = readln.chomp.to!int; auto C = N.iota.map!(_ => readln.split.map!(to!int).array).array; C.sort!"a[0] - a[1] < b[0] - b[1]"(); auto LIS = new int[](N + 1); LIS.fill(-INF); LIS[0] = INF; for (int i = 0; i < N; ) { Tuple!(int, int)[] tmp; do { auto lb = LIS.assumeSorted!"a > b".lowerBound(C[i][0] + C[i][1]).length.to!int; tmp ~= tuple(lb, C[i][0] + C[i][1]); ++i; } while (i < N && C[i][1] - C[i][0] == C[i-1][1] - C[i-1][0]); foreach (t; tmp) LIS[t[0]] = max(LIS[t[0]], t[1]); } (N + 1).iota.filter!(i => LIS[i] != -INF).reduce!max.writeln; }