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