这道题相当的经典，本身就有很多做法，而CQF大牛的做法尤为精妙。

给出一系列零件Si，零件有两个参数Ai Bi。现在将其排序，要求若i>j，则Ai>=Aj Bi>=Bj。也就是前面的两个参数要分别小于等于后面的两个参数。求此队列的最大长度。

那么如果将其投影到二维平面上，对每个零件Ai Bi点计数，那么问题就转换成为从最左下的1 1到左上的100 100，只能向右和向上运动，求运动过程中的访问总和最大值。

因此只要把每个点下面和左面的点比较，大者记入此点总和即可。

今天偶然看了一下排名，ZOJ果然有没落的倾向，而据说POJ越来越繁荣了。

#include <cstdio>
#include <string>

int n, a[101][101], b[101][101], nx, ny, mx, my;

int maxi ( int a, int b )
{
 return a > b ? a : b;
}

void pb ()
{
 //printf ( "%d %d %d %d\n", mx, my, nx, ny );
 int i, k;
 for ( i = nx; i <= mx; i ++ )
 {
  for ( k = ny; k <= my; k ++ )
  {
   printf ( "%d ", b[i][k] );
  }
  printf ( "\n" );
 }
}

void init ()
{
 memset ( a, 0, sizeof (a) );
 memset ( b, 0, sizeof (b) );
 mx = my = 0, nx = ny = 101;
}

int dp ()
{
 int i, k;
 for ( i = nx; i <= mx; i ++ )
 {
  for ( k = ny; k <= my; k ++ )
  {
   b[i][k] = maxi ( b[i - 1][k], b[i][k - 1] );
   if ( a[i][k] ) b[i][k] += a[i][k];
  }
 }
 //pb ();
 return b[mx][my];
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 while ( scanf ( "%d", &n ) )
 {
  if ( !n ) 
  {
   printf ( "*\n" );
   break;
  }
  int i, x, y;
  init ();
  for ( i = 0; i < n; i ++ )
  {
   scanf ( "%d %d", &x, &y );
   a[x][y] ++;
   if ( x > mx ) mx = x;
   if ( y > my ) my = y;
   if ( x < nx ) nx = x;
   if ( y < ny ) ny = y;
  }
  printf ( "%d\n", dp () );
 }
 return 0;
}
  

评论