Follows 103.c (Total 115 lines):

/* @JUDGE_ID:4461XX 103 C "LIS" */
/* A */
#include<stdio.h>
#define MAX_D 10
#define MAX_N 30

struct Box{
    int index ;
    int wid[MAX_D] ;
} ;
struct LIS{
	int from ;
	int len ;
} ;

struct Box box[MAX_N] ;
struct LIS lis[MAX_N] ;
int n , d ;

void Input( void )
{
	int i , j , k , tmp ;

	for( i=0 ; i<n ; ++i ){
		box[i].index = i+1 ;

		for( j=0 ; j<d ; ++j ) scanf( "%d" , &box[i].wid[j] ) ;
		for( j=0 ; j<d ; ++j ) /* sort */
			for( k=j+1 ; k<d ; ++k )
				if( box[i].wid[j]>box[i].wid[k] ){
					tmp = box[i].wid[j] ;
					box[i].wid[j] = box[i].wid[k] ;
					box[i].wid[k] = tmp ;
				}
	}
}
int needswap( int b1 , int b2 )
{
	int i ;

	for( i=0 ; i<d&&box[b1].wid[i]==box[b2].wid[i] ; ++i ) ;
	
	if( box[b1].wid[i]>box[b2].wid[i] ) return 1 ;
	else return 0 ;
}
void swap( int b1 , int b2 )
{
	int i ;

	box[b1].index ^= box[b2].index ^= box[b1].index ^= box[b2].index ;
	
	for( i=0 ; i<d ; ++i )
		box[b1].wid[i] ^= box[b2].wid[i] ^= box[b1].wid[i] ^= box[b2].wid[i] ;
}
void Sort( void )
{
	int i , j ;

	for( i=0 ; i<n ; ++i )
		for( j=i+1 ; j<n ; ++j )
			if( needswap( i , j ) ) swap( i , j ) ;
}
int canput( int b1 , int b2 )
{
	int i ;

	for( i=0 ; i<d ; ++i )
		if( box[b1].wid[i]>=box[b2].wid[i] ) return 0 ;

	return 1 ;
}
void LIS( void )
{
	int i , j ;

	for( i=0 ; i<n ; ++i ){ /* initial */
		lis[i].from = -1 ;
		lis[i].len = 1 ;
	}
	
	for( i=0 ; i<n ; ++i )
		for( j=i-1 ; j>=0 ; --j )
			if( canput( j , i ) )
				if( lis[j].len+1>lis[i].len ){
					lis[i].len = lis[j].len+1 ;
					lis[i].from = j ;
				}
}
void Output( void )
{
	int i , max , ans[MAX_N] , tmp ;

	for( max=i=0 ; i<n ; ++i ) /* find max */
		if( lis[i].len>lis[max].len ) max = i ;
	printf( "%d\n" , lis[max].len ) ;
	
	for( i=lis[max].len-1,tmp=max ; i>=0 ; --i ){
		ans[i] = box[tmp].index ;
		tmp = lis[tmp].from ;
	}
	printf( "%d" , ans[0] ) ;
	for( i=1 ; i<lis[max].len ; ++i ) printf( " %d" , ans[i] ) ;
	putchar( '\n' ) ;
}
int main( void )
{
    while( scanf( "%d %d" , &n , &d )==2 ){
		Input() ;
		Sort() ;
		LIS() ;
		Output() ;
    }

    return 0 ;
}

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com