1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #include<bits/stdc++.h> #define M 30010 #define N 10010 #define max(a,b) ((a)>(b)?(a):(b)) #define fsb(a,b,c) for(int a=b;a<=c;a++) #define fbs(a,b,c) for(int a=b;a>=c;a--) using namespace std; struct node{ int s,nt; }a[N]; int f[M],n,mx,head[M],x,y; template<typename T>inline void rll(T &x){ T f=1;x=0;char c=getchar(); while(!isdigit(c))f=c=='-'?-1:f,c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); x*=f; } inline void add(int x,int y,int i){ a[i].s=y;a[i].nt=head[x];head[x]=i; } int main(){ rll(n);mx=0;memset(head,255,sizeof(head)); fsb(i,1,n){ rll(x),rll(y);x++;y++; add(y,x,i);mx=max(mx,y); } f[0]=0; fsb(i,1,mx){ f[i]=f[i-1]; for(int t=head[i];t!=-1;t=a[t].nt) f[i]=max(f[i],f[a[t].s]+i-a[t].s); } printf("%d\n",f[mx]); return 0; }
|