|
|
back to boardWA on test 1,it is terrible! #include <iostream> using namespace std; int main () { long n; long i,j,k,p; long zz,maxn,nowmax,wz; long l[100],r[100]; long xout[100],yout[100]; long much[100]; long shangyige[100]; for (i=0;i<100;i++) { l[i]=0; r[i]=0; much[i]=0; xout[i]=0; yout[i]=0; shangyige[i]=0; } cin>>n; for (i=1;i<=n;i++) { cin>>l[i]>>r[i]; if (l[i]>r[i]) { zz=l[i]; l[i]=r[i]; r[i]=zz; } } for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (l[i]>l[j]) { zz=l[i]; l[i]=l[j]; l[j]=zz; zz=r[i]; r[i]=r[j]; r[j]=zz; } maxn=0; much[1]=1; shangyige[1]=0; for (i=2;i<=n;i++) { nowmax=0; for (j=1;j<i;j++) { p=1; k=j; while (k!=0) { if ((l[k]<r[i])&&(r[k]>r[i])) { p=0; break; } k=shangyige[k]; } if (p==1) { if (much[j]>nowmax) { nowmax=much[j]; wz=j; } } } if (nowmax==0) { much[i]=1; shangyige[i]=0; } else { much[i]=nowmax+1; shangyige[i]=wz; } } nowmax=0; for (i=1;i<=n;i++) if (much[i]>nowmax) { nowmax=much[i]; wz=i; } cout<<nowmax<<endl; i=wz; j=1; while (i!=0) { xout[j]=l[i]; yout[j]=r[i]; j++; i=shangyige[i]; } for (i=1;i<j;i++) cout<<xout[i]<<" "<<yout[i]<<endl; return (0); } |
|
|