https://emtubasa.hateblo.jp/entry/2019/01/01/152615

解法

区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。
まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標 $x$ と $r$ がわかっているとき、円と軸が接する2点は、 $x-r$ と $x+r$ になります。
すると、この $x-r$ から $x+r$ を、一つの区間としてみることができます。 $i$ 番目の円 $C_i$ に対する $x_i - r_i$ を $L_i$ 、 $x_i + r_i$ を $R_i$ とします。
あるサイズのターゲットが存在するとき、もう一つサイズを増やすには、
今あるターゲットの中で最大の円 $C_i$ と、新しく加わる円 $C_j$ が次のような関係になっている必要があります。
$L_j \lt L_i$ かつ $R_i \lt R_j$
図で表すとこのような状態です。 f:id:emtubasa:20190101125255p:plain
さて、ここで区間スケジューリングのように、区間の終わり、つまり $R$ 側に注目すると、 $R$ を降順でソートすることで、円をいくつか選び、その円でサイズ $K$ のターゲットが作成できたとき、 $K$ 個を大きさ順に並べると、上のソートした順番と同じになります。
ので、 $R$ について降順でソートしておけば、あとは $L$ についてのみ考慮すれば、前から順番に円を選んでいくだけでターゲットが作成できるということです。
としたいのですが、コーナーケースが存在します。 $R_i = R_j$ となるようなケースになります。このような場合は、 $L$ について昇順になっていると、 $L_i$ と $L_j$ のみでターゲットのサイズを増やせるかどうかの判定ができないので、降順にならべておけばよいです。

ここで、LISを思い出すことができれば、
$dp[K] =$ サイズ $K$ のターゲットを作成できるとき、その中で最小の円 $c_i$ についての $L_i$ の最小値
とすると、この問題を解くことができます。
円 $c_j$ を合わせてサイズ $K+1$ のターゲットを作成するときに必要な条件が、 $L_i \lt L_j$ であるので、 $L_i$ はできるだけ小さくしておきたいからです。
$dp[K]$ の中の要素は昇順に並んでいますので、 $c_i$ について見ているとき、 $L_i$ のlower_boundを探しその部分を更新していき、なければ今最大の $K$ に1追加した場所、つまり $dp[K+1]$ に $L_i$ を格納する、という操作を行えばよいです。これを $N$ 回繰り返すと、値が格納されている $K$ のうち最大の値が答えになります。