fork download
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. #define MAX 10010
  6. struct block{
  7. int l;
  8. int m;
  9. };
  10. block a[MAX];
  11. int val[MAX];
  12. bool compare(const block& lhs, const block& rhs){
  13. if(lhs.l != rhs.l)
  14. return lhs.l<rhs.l;
  15. return lhs.m < rhs.m;
  16. }
  17. int lis(int n){
  18. if(n==0) return val[n]=1;
  19. if(val[n]!=-1) return val[n];
  20. int max=0;
  21. for(int i=0;i<n;i++){
  22. if(a[i].m<=a[n].m){
  23. int temp=lis(i);
  24. if(max<temp) max=temp;
  25. }
  26. }
  27. return val[n]=max+1;
  28. }
  29. int main()
  30. {
  31. //freopen("in.txt","r",stdin);
  32. //freopen("out.txt","w",stdout);
  33. int n;
  34. while(scanf("%d",&n)&&n!=0){
  35. memset(val,-1,sizeof val);
  36. for(int i=0;i<n;i++){
  37. scanf("%d %d",&a[i].l,&a[i].m);
  38. }
  39. sort(a,a+n,&compare);
  40. int total=0;
  41. for(int i=0;i<n;i++){
  42. int temp=lis(i);
  43. if(total<temp) total=temp;
  44. }
  45. printf("%d\n",total);
  46. }
  47. printf("*\n");
  48. }
  49.  
Success #stdin #stdout 0s 3264KB
stdin
3
3 2
1 1
2 3
5
4 2
2 4
3 3
1 1
5 5
0
stdout
2
3
*