CFR 489 B. BerSU Ball ( DP )

Problem - B - Codeforces
題意：
給兩個不一定等長序列，求最大配對數，使得每個配對的權值差不超過 1。
解法：
dp[ i ][ j ] : 已考慮前 i 個第一序列的數，已考慮前 j 個第二序列的數，此時的最大配對數。
dp[ i ][ j ] = max{ dp[ i - 1 ][ j ], dp[ i ][ j - 1 ], dp[ i - 1 ][ j - 1 ] + 1 if A[ i ] == B[ j ] }

int N;
vi A;
int M;
vi B;

void init(){
	cin >> N;
	A = vi( N );
	for( int i = 0; i < N; ++i )
		cin >> A[ i ];
	cin >> M;
	B = vi( M );
	for( int i = 0; i < M; ++i )
		cin >> B[ i ];
}

void preprocess(){
	sort( A.begin(), A.end() );
	sort( B.begin(), B.end() );
}

void solve(){
	vvi dp( A.size() + 1, vi( B.size() + 1 ) );
	for( int i = 0; i <= A.size(); ++i )
		for( int j = 0; j <= B.size(); ++j ){
			if( i < A.size() )
				upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] );
			if( j < B.size() )
				upmax( dp[ i ][ j + 1 ], dp[ i ][ j ] );
			if( i < A.size() and j < B.size() and abs( A[ i ] - B[ j ] ) <= 1 )
				upmax( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + 1 );
		}
	cout << dp[ A.size() ][ B.size() ] << endl;
}