这道题相当的经典，本身就有很多做法，而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;}   2210940 2007-01-27 21:57:54 Accepted 1787 C++ 00:00.01 472K Crux.D    

评论