Follows 231.c (Total 46 lines):

/* @JUDGE_ID:4461XX 231 C "Longest Decreasing Subsequence" */
/* A */
#include<stdio.h>
#define MAX 1000000

int num[MAX] ;
int lds[MAX] ;
int len ;

int LDS( void )
{
	int i , j ;

	for( i=0 ; i<len ; ++i )
		for( j=i-1,lds[i]=1 ; j>=0 ; --j )
			if( num[j]>num[i] )
				if( lds[j]+1>lds[i] ) lds[i] = lds[j]+1 ;
	for( i=1,j=lds[0] ; i<len ; ++i )
		if( lds[i]>j ) j=lds[i] ;

	return j ;
}
int main( void )
{
	int i , n , case_time ;
	int firstOutput=1;
	for( case_time=1 ; scanf( "%d" , &n )==1 ; ++case_time ){
		if( n==-1 ) break ;
		
		num[0] = n ;
		for( i=1 ; ; ++i ){
			scanf( "%d" , &num[i] ) ;
			if( num[i]==-1 ) break ;
		}
		len = i ;

		if( firstOutput ){
			firstOutput = 0;
			printf( "Test #%d:\n  maximum possible interceptions: %d\n" , case_time , LDS() ) ;
		}
		else
			printf( "\nTest #%d:\n  maximum possible interceptions: %d\n" , case_time , LDS() ) ;
	}

	return 0 ;
}

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