CFR 4 D. Mysterious Present ( DP )

Problem - D - Codeforces
題意：
給 N 張卡片，各有固定的長寬( 不可調換 )，和一張必須是第一張的卡及其長寬，求最長的序列，滿足左邊的卡長寬皆嚴格小於右邊的卡。
解法：
首先刪去無法容下第一張卡片的所有卡片，就能無視第一張卡。接著對剩下的卡片做排序，就能轉為 DAG 上的動態規劃。
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 ];
}