将区间按左端点排序。
f(i)=max{f(j)+1}(p[j].x+p[j].y<=p[i].x && j<i)
#include<cstdio> #include<algorithm> using namespace std; int n,f[10001]; struct Point{int x,y;}p[10001]; bool operator < (const Point &a,const Point &b){return a.x<b.x;} int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+1+n); for(int i=1;i<=n;++i) f[i]=1; for(int i=1;i<=n;++i) for(int j=1;j<i;++j) if(p[j].x+p[j].y<=p[i].x) f[i]=max(f[j]+1,f[i]); printf("%d\n",*max_element(f+1,f+n+1)); return 0; }