题意
在一条直线上有 $n$ 个圆，分别以 $c_i$ 为圆心，$r_i$ 为半径。
如果两个圆相离、相切、包含时，这两个圆可以放在一起，求最多能有多少个圆同时放在一起，求方案。
$1 \leq n \leq 2000$
题解
首先可以把一个圆看作一条线段 $\left[c_i - r_i, c_i + r_i\right]$。离散化。
设 $f_{l, r}$ 表示只考虑左右端点都在 $\left[l, r\right]$ 中的线段，最多能选几个。
有转移 $f_{l, r} = \max\left(f_{l, i} + f_{i, r}\right)$，但如果正好有一条 $\left[l, r\right]$ 的线段，那么显然这条线段也可以选，$f_{l, r}$ 要额外加 $1$。
这样是 $O\left(n^3\right)$ 的，但是我们发现并不是所有的 $i$ 都有效，我们只需要枚举所有起点为 $l$ 的线段的右端点作为 $i$ 即可。
代码
/* C++20 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* 我还期待着名为奇迹的魔法，哪怕会凋零会消散只会是一场浮华，我笑纳！
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#define __NO_MAIN__ false
constexpr bool _MTS = false, SPC_MTS = false;
#include <bits/stdc++.h>
#define FULL(arg) arg.begin(), arg.end()
// :/
using namespace std;
using tp = long long int;
using vetp = vector<tp>;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 2;
int STRUGGLING(unsigned long long int);
void MIST();
#if !__NO_MAIN__
int main(int argc,char* argv[]){unsigned long long int t=0,_t=1;MIST();if(_MTS&&
!SPC_MTS)cin>>_t;while(t<_t||SPC_MTS){if(STRUGGLING(++t)!=0)return 0;}return 0;}
#endif
template <typename _Ty> class _Lambda_t {_Ty lexp;public:template<typename __Ty>
_Lambda_t(__Ty&&lexp):lexp(static_cast<__Ty&&>(lexp)){}template<typename... __Ty
>decltype(auto)operator()(__Ty&&...args){return lexp(std::ref(*this),static_cast
<__Ty&&>(args)...); } }; template <typename _Ty> decltype(auto) lexp(_Ty&&l_exp)
{ return _Lambda_t<typename std::decay<_Ty>::type>(static_cast<_Ty&&>(l_exp)); }
#ifdef XCODE
#define bg(...){cout<<"["<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' << " <<:" << endl; } template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#define dputs(...)
#endif
// :/
// :/
int STRUGGLING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
tp n; cin >> n;
vector<pair<tp, tp>> a(n);
vetp all;
map<pair<tp, tp>, tp> gid;
for (tp i = 0; i < n; ++i) {
tp c, r; cin >> c >> r;
a[i].first = c - r;
a[i].second = c + r;
}
for (tp i = 0; i < n; ++i) all.push_back(a[i].first);
for (tp i = 0; i < n; ++i) all.push_back(a[i].second);
stable_sort(FULL(all));
all.erase(unique(FULL(all)), all.end());
auto id = [&](tp x) -> tp { return lower_bound(FULL(all), x) - all.begin(); };
for (tp i = 0; i < n; ++i) a[i].first = id(a[i].first);
for (tp i = 0; i < n; ++i) a[i].second = id(a[i].second);
for (tp i = 0; i < n; ++i) gid[a[i]] = i + 1;
vector<vetp> s(all.size());
for (tp i = 0; i < n; ++i) s[a[i].first].push_back(a[i].second);
vector<vetp> f(all.size(), vetp(all.size()));
vector<vetp> g(all.size(), vetp(all.size()));
for (tp len = 1; len <= all.size(); ++len) {
for (tp l = 0; l + len - 1 < all.size(); ++l) {
tp r = l + len - 1, os = 0;
if (l < r) {
if (f[l][r - 1] > f[l + 1][r]) {
f[l][r] = f[l][r - 1];
g[l][r] = r - 1;
} else {
f[l][r] = f[l + 1][r];
g[l][r] = l + 1;
}
}
for (auto& i : s[l]) {
if (i == r) os = 1;
if (i < r && f[l][i] + f[i][r] > f[l][r]) {
f[l][r] = f[l][i] + f[i][r];
g[l][r] = i;
}
}
f[l][r] += os;
}
}
cout << f[0].back() << '\n';
auto go = lexp([&](auto $, tp l, tp r) -> void {
if (gid.count(make_pair(l, r))) cout << gid[make_pair(l, r)] << ' ';
if (r - l <= 1) return;
$(l, g[l][r]);
$(g[l][r], r);
});
go(0, all.size() - 1);
cout << '\n';
return 0;
}
void MIST() {
cin.tie(nullptr)->sync_with_stdio(false);
}
// :\ */