# CFR 4 D. Mysterious Present ( DP )

Problem - D - Codeforces

dp[ i ] : 已考慮前 i 張卡，此時最大可能長度。
dp[ i ] = max{ dp[ j ] | j < i and W[ j ] < W[ i ] and H[ j ] < H[ i ] }

```int N, MNW, MNH;
vi W, H;

void init(){
cin >> N >> MNW >> MNH;
W = H = vi( N );
for( int i = 0; i < N; ++i )
cin >> W[ i ] >> H[ i ];
}

typedef tuple< int, int, int > t3i;
typedef vector< t3i > vt3i;

vt3i card;
vi dp;
vi pre;

void preprocess(){
for( int i = 0; i < N; ++i ){
if( not ( MNW < W[ i ] and MNH < H[ i ] ) )
continue;
card.emplace_back( W[ i ], H[ i ], i );
}
sort( card.begin(), card.end() );
N = card.size();
dp = vi( N );
pre = vi( N, -1 );
for( int i = 0; i < N; ++i )
dp[ i ] = 1;
for( int i = 0; i < N; ++i )
for( int j = i + 1; j < N; ++j ){
int w1, h1, x1; tie( w1, h1, x1 ) = card[ i ];
int w2, h2, x2; tie( w2, h2, x2 ) = card[ j ];
if( not ( w1 < w2 and h1 < h2 ) )
continue;
if( upmax( dp[ j ], dp[ i ] + 1 ) )
pre[ j ] = i;
}
}

void solve(){
int ans = 0, e = -1;
for( int i = N - 1; i >= 0; --i )
if( upmax( ans, dp[ i ] ) )
e = i;
cout << ans << endl; if( ans == 0 ) return;
stack< int > stk;
for( ; ~e; e = pre[ e ] )
stk.emplace( e );
for( ; not stk.empty(); stk.pop() )
cout << get< 2 >( card[ stk.top() ] ) + 1 << " \n"[ ( int ) stk.size() == 1 ];
}
```