题意：
在一条直线上有n个圆，分别以c[i]为圆心，r[i]为半径。
如果两个圆属于相离、相切、包含关系时，这两个圆可以放在一起，
求最多能有多少个圆同时放在一起，输出个数，并在第二行分别输出它们的序号，
序号无需排序。
思考：
（大学阶段第一道题）好久不做普通dp题（好久没碰代码了），但是可以看出他是dp题。
用 $f[i][j]$ 表示从第 $i$ 个圆开始，考虑所有左端点不超过 $j$ 的圆 ， 最多选几个圆。
$f[i][j]=max(f[i+1][j],f[i+1][r[i]]+f[nxt[i]][j]+1)$ 一种是不选它直接转移，另一种是选它然后从nxt（比这个圆靠右但是不相交的）往后选。复杂度$O(n^2)$
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 const int maxn=2010; 5 int dp[2010][2010],Rd[2010],R[2010],nxt[2010]; 6 struct NODE{ 7 int l,r,id; 8 }d[maxn]; 9 bool cmp(const NODE&x,const NODE&y){ 10 if(x.l!=y.l)return x.l<y.l; 11 else return x.r>y.r; 12 } 13 void dfs(int x,int y){ 14 if(x==n+1)return; 15 if(dp[x][y]==dp[x+1][y]){dfs(x+1,y);return;} 16 printf("%d ",d[x].id); 17 dfs(x+1,Rd[x]);dfs(nxt[x],y); 18 } 19 int main(){ 20 int a,b,i,j; 21 scanf("%d",&n); 22 for(i=1;i<=n;i++){ 23 scanf("%d%d",&a,&b); 24 d[i].l=a-b;d[i].r=a+b; 25 d[i].id=i;R[i]=d[i].r; 26 }sort(d+1,d+n+1,cmp); 27 sort(R+1,R+n+1); 28 for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(d[i].r==R[j])Rd[i]=j; 29 for(i=1;i<=n;i++){ 30 nxt[i]=n+1; 31 for(j=1;j<=n;j++)if(d[i].r<=d[j].l){nxt[i]=j;break;} 32 }for(i=n;i>=1;i--){ 33 for(j=1;j<=n;j++){ 34 dp[i][j]=dp[i+1][j]; 35 if(d[i].r<=R[j]) 36 dp[i][j]=max(dp[i][j],dp[i+1][Rd[i]]+dp[nxt[i]][j]+1); 37 } 38 } 39 printf("%d\n",dp[1][n]); 40 dfs(1,n); 41 return 0; 42 }