BZOJ-1046: [HAOI2007]上升序列（LIS）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1046

首先用lis-dp暴力求出以每个开始的上升序列的长度，然后暴力O(nm)找

代码：

dcc451da81cb39dbf476c437d2160924ab183018.jpg.png

#include <iostream>
#include <algorithm>
#include <cstring>
  
using namespace std ;
  
#define MAXN 10010
#define lowbit( x ) ( ( - x ) & x )
  
struct saver {
       int v , t ;
} a[ MAXN ] ;
  
int n , m ;
  
bool cmp( saver x , saver y ) {
     return x.v > y.v ;
}
  
struct Bit {
       int t[ MAXN ] , N ;
         
       void Init( int _N ) {
            memset( t , 0 , sizeof( t ) ) ;
            N = _N ;
       }
         
       void Add( int x , int y ) {
            for ( int i = x ; i <= N ; i += lowbit( i ) ) t[ i ] = max( t[ i ] , y ) ;
       }
         
       int Max( int x ) {
           int rec = 0 ; 
           for ( ; x ; x -= lowbit( x ) ) rec = max( t[ x ] , rec ) ;
           return rec ;
       }
         
} bit ;
  
int rank[ MAXN ] , N = 0 , f[ MAXN ] , c[ MAXN ] ;
  
void Solve( int x ) {
     int w = x , u = - 0x7fffffff , ans[ MAXN ] ;
     ans[ 0 ] = 0 ;
     for ( int i = 0 ; i ++ < n ; ) if ( f[ i ] >= w && c[ i ] > u ) {
         ans[ ++ ans[ 0 ] ] = c[ i ] ; 
         u = c[ i ] , w -- ;
     }
     if ( ans[ 0 ] >= x ) {
          for ( int i = 0 ; i ++ < x - 1 ; ) cout << ans[ i ] << " " ; cout << ans[ x ] << endl ;
     } else cout << "Impossible\n" ;
}
  
int main(  ) {
    cin >> n ; for ( int i = 0 ; i ++ < n ; ) cin >> a[ i ].v , a[ i ].t = i , c[ i ] = a[ i ].v ;
    sort( a + 1 , a + n + 1 , cmp ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        if ( ! ( i - 1 ) || a[ i ].v != a[ i - 1 ].v ) ++ N ;
        rank[ a[ i ].t ] = N ;
    }
    bit.Init( N ) ;
    memset( f , 0 , sizeof( f ) ) ;
    for ( int i = n ; i ; i -- ) {
        f[ i ] = bit.Max( rank[ i ] - 1 ) + 1 ;
        bit.Add( rank[ i ] , f[ i ] ) ;
    }
    cin >> m ;
    while ( m -- ) {
          int x ; cin >> x ;
          Solve( x ) ;
    }
    return 0 ;
}