最长上升子序列（长度）

[cpp]?
#include??
#include??
#include??
?
using namespace std;??
int n ;?
const int maxn = 500005 ;?
int dp[ maxn ] , a[ maxn ];?
?
int LIS(int n )?
{?
??? int low , len , high , mid ;?
??? len = 1 ;?
??? //? mid = ( low + high ) / 2 ;??
??? dp[ 1 ] = a[ 1 ] ;?
??? for( int i = 2 ; i <= n ; i++ )?
??? {?
??????? low = 1 ;?
??????? high = len ;?
??????? while( low <= high )?
??????? {?
??????????? mid = ( low + high ) / 2 ;?
??????????? if( a[ i ] > dp[ mid ] )?
???????????????? low = mid + 1 ;?
??????????? else?
??????????????? high = mid - 1 ;?
??????? }?
??????? dp[ low ] = a[ i ] ;?
??????? if( low > len )?
??????????? len = low ;?
??? }?
??? return len ;?
}?
??
?
int main()?
{?
??? int i , j , n ;??
??? int flag = 1 ;?
??? while( ~scanf( "%d" , &n )? )?
??? {?
??????? memset( dp , 0 ,sizeof( dp ) ) ;?
??????? memset( a , 0 ,sizeof( a ) ) ;?
??????? for( i = 0 ; i < n ; ++i )?
??????? {?
??????????? int x , y ;?
??????????? scanf( "%d%d" , &x , &y );?
??????????? a[ x ] = y ;?
??????? }?
??????? int ans = LIS( n ) ;?
??????? printf( "Case %d:\n" , flag++ ) ;?
??????? if( ans == 1 )???
??????????? printf( "My king, at most 1 road can be built.\n" ) ;?
??????? else?
??????????? printf( "My king, at most %d roads can be built.\n" , ans ) ;?
??????? printf( "\n" ) ;?
??? }?
??? return 0? ;?
}?

#include
#include
#include

using namespace std;
int n ;
const int maxn = 500005 ;
int dp[ maxn ] , a[ maxn ];

int LIS(int n )
{
?int low , len , high , mid ;
?len = 1 ;
?//?mid = ( low + high ) / 2 ;
?dp[ 1 ] = a[ 1 ] ;
?for( int i = 2 ; i <= n ; i++ )
?{
??low = 1 ;
??high = len ;
??while( low <= high )
??{
???mid = ( low + high ) / 2 ;
???if( a[ i ] > dp[ mid ] )
???? low = mid + 1 ;
???else
????high = mid - 1 ;
??}
??dp[ low ] = a[ i ] ;
??if( low > len )
???len = low ;
?}
?return len ;
}
?

int main()
{
?int i , j , n ;?
?int flag = 1 ;
?while( ~scanf( "%d" , &n )? )
?{
??memset( dp , 0 ,sizeof( dp ) ) ;
??memset( a , 0 ,sizeof( a ) ) ;
??for( i = 0 ; i < n ; ++i )
??{
???int x , y ;
???scanf( "%d%d" , &x , &y );
???a[ x ] = y ;
??}
??int ans = LIS( n ) ;
??printf( "Case %d:\n" , flag++ ) ;
??if( ans == 1 )?
???printf( "My king, at most 1 road can be built.\n" ) ;
??else
???printf( "My king, at most %d roads can be built.\n" , ans ) ;
??printf( "\n" ) ;
?}
?return 0? ;
}

?