没这么复杂吧，链表也用了，排序之后就类似于最长递增子序列了。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

typedef struct {
    int D [1001] ;
}Ttype;
Ttype B[501];

int d;

int cmp ( const void *a , const void *b ) {
    Ttype *A = (Ttype *)a;
    Ttype *B = (Ttype *)b;
    return ( A->D[0] - B->D[0] ) ;
}

int Check ( int i , int j ) {
    int k;
    for ( k = 0 ; k < d ; k ++ ) {
        if ( B[i].D[k] >= B[j].D[k] ) return 0;
    }
    return 1;
}

int main(){
    int n , i , j , max , tmp , maxx ;
    bool m[501][501] ;
    int f[500] , G[1001]; 
    while ( scanf ( "%d%d" , &n , &d ) != EOF ) {
        for ( i = 0 ; i < d ; i++ ) scanf ( "%d" , G+i ) ;
        sort ( G , G + d ) ;

        for ( i = 0 ; i < n ; i++ ) {
            for ( j = 0 ; j < d ; j++) {
                scanf( "%d" , &B[i].D[j] ) ;
            }
            sort ( B[i].D , B[i].D + d ) ;
        }
        
        qsort ( B , n , sizeof ( Ttype ) , cmp ) ;

        memset ( m , 0 , sizeof( m ) ) ;
        for( i = 0 ; i < n ; i++ ) {
            for ( j = i + 1 ; j < n ; j++ ) {
                if ( Check ( i , j )  ) m [i][j] = 1;
            }
        }
        memset ( f , 0 , sizeof ( f ) ) ;
        maxx = 0 ;
        for ( i = n-1 ; i >= 0 ; i-- ) {
            max = 0;
            for ( j = i + 1 ; j < n ; j ++ ) {
                if ( m[i][j] && f[j] > max ) max = f[j] ;
            }
            f[i] = max + 1 ;
            if ( f[i] > maxx ) maxx = f[i] ;
        }

        max = 0 ;
        tmp = 0 ;
        for ( i = 0 ; i < n ; i ++ ) {
            for ( j = 0 ; j < d ; j ++ ) {
                if ( G[j] >= B[i].D[j] ) break;
            }
            if ( j == d  && f[i] > max ) {
                max = f[i] ;
                tmp = 1;
            }
        }
        if ( !tmp ) {
            printf ("Please look for another gift shop!\n");
            continue;
        }
        printf ("%d\n" , max ) ;
    }
    return 0;
}

• Just LCS~ (2218) busycai 2006-10-03 16:39:16