hdu1025-Constructing Roads In JGShinings Kingdom

最長上升子序列（長度）

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<cstring>  
 
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<iostream>
#include<cstdio>
#include<cstring>

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  ;
}