uva10635Prince and Princess(LIS)

제목: uva 10635 Prince and Princess (LIS)
제목 대의: 최 장 동일 한 공공 하위 서열 을 구하 세 요.
문제 풀이 방향: 데이터 가 많 기 때문에 62500 은 예전 의 LIS 를 구 하 는 방법 으로 할 수 없습니다.첫 번 째 노선 의 정 수 를 다시 정렬 할 수 있 습 니 다 (0... p). 그리고 그 다음 노선 은 같은 최 장 하위 서열 을 찾 아야 하기 때문에 원래 의 숫자 를 첫 번 째 노선 의 새로운 숫자 로 표시 해 야 합 니 다. 그러면 두 번 째 노선 의 LIS 만 찾 으 면 됩 니 다.
 nlog (n) 의 LIS 알고리즘:
                                일반적인 방법 은 찾 을 때 for 가 v [i] 보다 작은 수 를 찾 아야 합 니 다.
                                앞의 i 개 수의 최 장 LIS (top 은 0 부터) 를 LIS 배열 로 저장 합 니 다. 그러면 숫자 가 질서 있 게 2 분 으로 찾 을 수 있 습 니 다 (log (n). v [i] > LIS [top] 일 때 대 표 는 v [i] 를 더 해서 top + 1 길이 LIS 를 구성 할 수 있 습 니 다. 그래서 LIS [+ top] = v [i], dp [i] = top + 1;
                                만약 같 으 면 dp [i] = top + 1 을 설명 합 니 다. 그러나 작 으 면 LIS 에서 v [i] 와 같은 가장 가 까 운 v [i] 의 수 (k 번 째) 를 찾 아야 합 니 다. 이전의 k 개 수 는 모두 v [i] 보다 작 았 다 는 것 을 설명 합 니 다. 그러면 dp [i] = k + 1; 그러나 여기 있 는 LIS [k] 는 v [i] 로 업데이트 해 야 합 니 다.... 왜 그래 야 합 니까? k + 1 개의 길이 의 증가 서브 시퀀스 를 가 져 가 려 면 이전의 k 개 는 모두 같 기 때 문 입 니 다. 그러면 k + 1 개 에 대해 서 는 작은 것 을 가 져 가 는 것 이 좋 습 니 다. 그래 야 뒤의 숫자 가 이 서브 시퀀스 뒤에 연결 되 어 더 긴 서브 시퀀스 를 구성 할 수 있 기 때 문 입 니 다.       
코드:

#include <cstdio>
#include <cstring>

const int N = 62505;

int dp[N];
int v[N];
int vis[N];
int LIS[N];
int p1;

int Max (const int a, const int b) { return a > b ? a: b; }

int bsearch (int s) {

	int l = 0;
	int r = p1;
	int mid;
	while (l < r) {

		mid = l + (r - l) / 2;
		if (s == LIS[mid])
			return mid;
		else if (s > LIS[mid])
			l = mid + 1;
		else
			r = mid;
	}
	return l;
}

int main () {

	int n, p, q, t;
	scanf ("%d", &t);
	for (int cas = 1; cas <= t; cas++) {

		scanf ("%d%d%d", &n, &p, &q);
		memset (vis, -1, sizeof (vis));

		for (int i = 0; i <= p; i++) {
			scanf ("%d", &v[i]);
			vis[v[i]] = i;
		}

		p1 = -1;
		int k;
		int ans = 0;
		for (int i = 0; i <= q; i++) {
				
			scanf ("%d", &v[i]);
			v[i] = vis[v[i]];
			if (v[i] == -1)
				continue;
			if (p1 == -1) {
				dp[i] = 1;
				LIS[++p1] = v[i];
			} else {

				if (v[i] > LIS[p1]) {

					LIS[++p1] = v[i];
					dp[i] = p1 + 1;
				} else if (v[i] < LIS[p1]) {

					k = bsearch (v[i]);
					dp[i] = k + 1;
					LIS[k] = v[i];
				} else
					dp[i] = p1 + 1;
			}
			 ans = Max (ans, dp[i]);
		}
		printf ("Case %d: %d
", cas, ans);
	}
	return 0;
}