|
|
back to boardhere is my c++ code: #include <iostream.h> int main() { int n,i,j,x[501],z[501],aux,max,V[501],L[501],k,poz; cin>>n; for(i=1;i<=501;i++) z[i]=i; for(i=1;i<=n;i++) cin>>x[i]>>V[i]; if(n>1) { for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(x[i]<x[j]) { aux=x[i]; x[i]=x[j]; x[j]=aux; aux=V[i]; V[i]=V[j]; V[j]=aux; aux=z[i]; z[i]=z[j]; z[j]=aux; } } L[n]=1; for (k=n-1;k>=1;k--) { max=0; for (i=k+1;i<=n;i++) if ((V[i]>V[k])&&(L[i]>max)) max=L[i]; L[k]=max+1; } max=L[1]; poz=1; for (k=1;k<=n;k++) if (L[k]>max) { max=L[k]; poz=k; } cout<<max<<endl; cout<<z[poz]<<" "; for (i=poz+1;i<=n;i++) if ((V[i]>V[poz])&&(L[i]==max-1)) { cout<<z[i]<<" "; max--; } return 0; } I failed in #8 as well... Look at this: We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Pay attention to this: and their endpoints do not coincide. It means 3 4 and 4 4 coincide too! |
|
|