stick_ak.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>

ifstream fin("stick.in");
ofstream fout("stick.out");

struct point {
   int x, y; 
};

int cmp(const void* e1, const void* e2) {
   const point* p1 = (const point*)e1;
   const point* p2 = (const point*)e2;
   if (p1->x != p2->x) return p2->x - p1->x;
   return p2->y - p1->y;  
}

const int MAX = 5000+5;

int n;
point p[MAX];
int st[MAX];

main() {
   fin >> n;
   int i, j;
   for (i = 1; i <= n; i++)
      fin >> p[i].x >> p[i].y;
      
   qsort(&p[1], n, sizeof(p[0]), cmp);
   
   memset(st, 0, sizeof(st));
   for (i = 1; i <= n; i++)
      for (j = 0; j < i; j++)
         if (p[j].y < p[i].y && st[j] >= st[i])
            st[i] = st[j] + 1;
            
   int max = 0;
   for (i = 1; i <= n; i++)
      if (st[i] > max)
         max = st[i];
         
   fout << max << endl;
   
   return 0;  
}