POJ 2127 Greatest Common Increasing Subsequence ( DP )

2127 -- Greatest Common Increasing Subsequence

題意：
給兩個數列 A, B，長度分別為 N, M，求最長公共遞增子序列。

資料規模：
元素大小在 int32 範圍
N, M ≤ 500
TL: 2000 ms

解法：
顯然可以定義 O( N^3 ) 的 dp，但這裡考慮 O( N^2 )。
dp[ i ][ j ] : B[ j - 1 ] 為子序列的結尾的前提下，考慮 A[ 0, i ) 和 B[ 0, j ) 的最長公共子序列時的最長長度。
dp[ i ][ j ] = dp[ i - 1 ][ j ], if A[ i - 1 ] != B[ j - 1 ]
_______________best( i, j ), otherwise
best( i, j ) 的維護方法如此：在更新 dp 表格時，以 i = 1 -> N, j = 1 -> M 的順序進行。考慮到 j 那層迴圈，當我們要更新某個滿足 A[ i - 1 ] = B[ j - 1 ] 的 dp[ i ][ j ] 時，有某個 j' < j，使得 B[ j' - 1 ] < A[ i - 1 ]，顯然 dp[ i ][ j' ] 會滿足 j' < j 且 B[ j' - 1 ] < A[ i - 1 ] = B[ i - 1 ]，並且一定包含最大值。

時間 / 空間複雜度：
O( N^2 )

#include <bits/stdc++.h>
using namespace std;

signed main(){
  ios::sync_with_stdio( 0 );
  int N; cin >> N;
  vector< int > A( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  int M; cin >> M;
  vector< int > B( M );
  for( int i = 0; i < M; ++i ){
    cin >> B[ i ];
  }
  vector< vector< int > > dp( N + 1, vector< int >( M + 1 ) );
  vector< vector< int > > dc( N + 1, vector< int >( M + 1 ) );
  for( int i = 1; i <= N; ++i ){
    int best = 0, id = -1;
    for( int j = 1; j <= M; ++j ){
      if( A[ i - 1 ] == B[ j - 1 ] ){
        dp[ i ][ j ] = best + 1;
        dc[ i ][ j ] = id;
      } else{
        dp[ i ][ j ] = dp[ i - 1 ][ j ];
        if( B[ j - 1 ] < A[ i - 1 ] ){
          if( best < dp[ i ][ j ] ){
            best = dp[ i ][ j ];
            id = j;
          }
        }
      }
    }
  }
  int ans = 0, iid, jid;
  for( int i = 1; i <= N; ++i ){
    for( int j = 1; j <= M; ++j ){
      if( ans < dp[ i ][ j ] ){
        ans = dp[ i ][ j ];
        iid = i;
        jid = j;
      }
    }
  }
  cout << ans << endl;
  vector< int > stk;
  for( int i = 0, x = iid, y = jid; i < ans; ++i ){
    while( dc[ x ][ y ] == 0 ) --x;
    stk.emplace_back( B[ y - 1 ] );
    y = dc[ x ][ y ];
  }
  for( int i = ( int ) stk.size() - 1; i >= 0; --i ){
    cout << stk[ i ] << " \n"[ i == 0 ];
  }
  return 0;
}