題目：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 ;
}
