POJ 2127 Greatest Common Increasing Subsequence ( DP )

2127 -- Greatest Common Increasing Subsequence

N, M ≤ 500
TL: 2000 ms

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;
}
```