1025.txt

就是把所有递增序列放到一起

#include   <iostream>   
  #include   <vector>   
  #include   <algorithm>   
    
  #ifdef   DEBUG   
  #include   <fstream>   
  #endif   
    
  using   namespace   std;   
    
  const   int   MAX_N   =   5000;   
    
  #ifdef   DEBUG   
        ifstream   fin("1025.in");   
        ofstream   fdebug("debug.txt");   
        istream&   in     =   fin;   
        ostream&   out   =   cout;   
  #else   
        istream&   in     =   cin;   
        ostream&   out   =   cout;   
  #endif   
    
  struct   Stick   {   
        int   length,   weight;   
  };   
    
  bool   operator<(const   Stick&   x,   const   Stick&   y)   
  {   
        if   (x.length   !=   y.length)   {   
              return   (x.length   <   y.length);   
        }   else   {   
              return   (x.weight   <   y.weight);   
        }   
  }   
    
  #ifdef   DEBUG   
        ostream&   operator<<(ostream&   out,   const   Stick&   s)   
        {   
              out   <<   "("   <<   s.length   <<   ",   "   
                    <<   s.weight   <<   ")";   
              return   out;   
        }   
  #endif   
    
  Stick   sticks[MAX_N+1];   
  int   n;   
    
  int   SetupTime()   
  {   
        int   result   =   0;   
        sort(&sticks[0],   &sticks[n]);   
        bool   del[MAX_N+1];   
        memset(del,   false,   sizeof(del));   
    
        for   (int   i   =   0;   i   <   n;   i++)   {   
              if   (!del[i])   {   
                    result++;   
                    int   w   =   sticks[i].weight;   
                    for   (int   j   =   0;   j   <   n;   j++)   {   
                          if   ((!del[j])   &&   (sticks[j].weight   >=   w))   {   
                                w   =   sticks[j].weight;   
                                del[j]   =   true;   
                          }   
                    }   
              }   
        }   
        return   result;   
  }   
    
  int   main()   
  {   
        int   t;   
        in   >>   t;   
        for   (int   i   =   0;   i   <   t;   i++)   {   
              in   >>   n;   
              for   (int   j   =   0;   j   <   n;   j++)   {   
                    in   >>   sticks[j].length   
                          >>   sticks[j].weight;   
              }   
              out   <<   SetupTime()   <<   endl;   
        }   
    
        return   0;   
  }
 
其中：   
  for   (int   j   =   0;   j   <   n;   j++)   {   
                          if   ((!del[j])   &&   (sticks[j].weight   >=   w))   {   
                                w   =   sticks[j].weight;   
                                del[j]   =   true;   
                          }   
                    }   
  就是把所有递增序列放到一起，但是可不可能出现特殊情况呢？