Follows 10131.c (Total 86 lines):

/* @JUDGE_ID:4461XX 10131 C "DP - LDS( Longest Decreasing Subsequence ):P" */
/* A */
#include<stdio.h>
#define MAX 1000

typedef struct{
	int index ;
	int wei ;
	int iq ;
}ELEPHANT ;
typedef struct{
	int len ;
	int from ;
}ANS ;

ELEPHANT ele[MAX] ;
ANS ans[MAX] ;;

int input( void )
{
	int i ;

	for( i=0 ; scanf( "%d %d" , &ele[i].wei , &ele[i].iq )==2 ; i++ ) ele[i].index = i+1 ;
	
	return i ;
}
int sort_f( const void *a , const void *b )
{
	ELEPHANT *p , *q ;

	p = (ELEPHANT *)a ;
	q = (ELEPHANT *)b ;
	
	if( p->wei==q->wei )
		return p->iq-q->iq ;
	else
		return p->wei-q->wei ;
}
void LDS( int size )
{
	int i , j ;

	for( i=0 ; i<size ; i++ ){ /* initial */
		ans[i].len = 1 ;
		ans[i].from = -1 ;
	}
	
	for( i=0 ; i<size ; i++ ) /* DP */
		for( j=i-1 ; j>=0 ; j-- )
			if( ele[i].iq<ele[j].iq )
				if( ans[i].len<ans[j].len+1 ){
					ans[i].len = ans[j].len+1 ;
					ans[i].from = j ;
				}
}
int FindBig( int size )
{
	int i , max ;

	for( max=i=0 ; i<size ; i++ )
		if( ans[i].len>ans[max].len ) max = i ;

	return max ;
}
void print( int size )
{
	int big , a_out[MAX+1] , i ;

	big = FindBig( size ) ;
	printf( "%d\n" , ans[big].len ) ;

	for( i=big ; i!=-1 ; i=ans[i].from ) a_out[ ans[i].len ] = ele[i].index ;
	for( i=1 ; i<=ans[big].len ; i++ ) printf( "%d\n" , a_out[i] ) ;
}
int main( void )
{
	int size ;
	
	size = input() ;
	qsort( (void *)ele , size , sizeof( ELEPHANT ) , sort_f ) ;
	LDS( size ) ; /* longest decreasing subsequence( iq ) */
	print( size ) ;
	
	return 0 ;
}
/* @END_OF_SOURCE_CODE */

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