UVa-10635 : Prince and Princess

問題概要

長さL(<250^2)の値が重複しない数列がそれぞれ2つずつ与えられる。最長共通部分列を求める問題。

解法

片方の数列に現れる順序で数字に番号を振りなおして、もう片方の数列で最長増加部分列を求めればよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 250;
const int MAX_M = MAX_N * MAX_N;
const int INF = 1<<29;

int as[MAX_M], bs[MAX_M], order[MAX_M + 1];
int N, A, B;
int dp[MAX_M + 1];

void init(){
	scanf("%d%d%d", &N, &A, &B);
	A++; B++;
	for(int i=0; i<A; i++){
		scanf("%d", as+i);
	}
	for(int i=0; i<B; i++){
		scanf("%d", bs+i);
	}
}

int solve(){
	fill(order, order+MAX_M+1, INF);
	for(int i=0; i<A; i++){
		order[as[i]] = i;
	}
	for(int i=0; i<B; i++){
		bs[i] = order[bs[i]];
	}


	fill(dp, dp+MAX_M+1, INF);

	for(int i=0; i<B; i++){
		*lower_bound(dp, dp+MAX_M+1, bs[i]) = bs[i];
	}

	int ans = 0;
	for(int i=0; i<=MAX_M; i++){
		if(dp[i] < INF){
			ans = i + 1;
		}
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	for(int c=1; c<=T; c++){
		init();
		printf("Case %d: %d\n", c, solve());
	}

	return 0;
}