14-高效求最长公共子序列(二维数组存不下)

/* See LCS again
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
There are A, B two sequences, the number of elements in the sequence is n、m;
Each element in the sequence are different and less than 100000.
Calculate the length of the longest common subsequence of A and B.
输入
The input has multicases.Each test case consists of three lines;
The first line consist two integers n, m (1 < = n, m < = 100000);
The second line with n integers, expressed sequence A;
The third line with m integers, expressed sequence B;
输出
For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.
样例输入
5 4
1 2 6 5 4
1 3 5 4
样例输出
3
*/
//题意是要求公共子序列的长度，并且保证输入串中每串数字中没有重复的数字；
//由于题目给的数据要求太大，故用一般的二维数组dp内存就超了，所以借鉴了一个大牛的技巧，将问题转化为求最长上
//升子序列。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int b[N];

int find(int l, int r, int k){
	while(l < r){
		int mid = (l + r) / 2;
		if(a[mid] == k){
			return mid;
		}
		else if(a[mid] > k){
			r = mid;
		} 
		else{
			l = mid + 1;
		}
	}
	return r;
}

int main(){
	std::ios::sync_with_stdio(false);
	int n, m;
	while(cin >> n >> m){
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		int x;
		for(int i = 1; i <= n; i++){
			cin >> x;
			a[x] = i;     //将第一串数字，标记在a数组中，将对应位置存为对应数字出现的序号 
		}
		int ct = 0;
		for(int i = 1; i <= m; i++){
			cin >> x;
			if(a[x]){			//看该数字是否在第一串数字中出现 
				b[ct++] = a[x];  //将公共数字出现的序号存下来，所以后面最长上升子序列就是两串数字的公共子序列个数
			}
		}
		int t = 0;
		a[t] = b[0];
		for(int i = 1; i < ct; i++){
			if(b[i] > a[t]){
				a[++t] = b[i];
			}
			else{
//				int w = find(0, t, b[i]);
				int w = lower_bound(a, a + t, b[i]) - a; //注意lower_bound 的用法，lower_bound返回的是一个地址
				a[w] = b[i];
			}
		}
		cout << t + 1<< endl;
	}
	return 0;
} 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int a[100005];
int b[100005];
int find(int *c, int low, int high, int x){
while(low < high){
int mid = (low + high) / 2;
if(x < c[mid]){
high = mid;
}
else{
low = mid + 1;
}
}
return low;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int x = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &x);
a[x] = i; //将第一串数字，标记在a数组中，将对应位置存为对应数字出现的序号
}
int y = 0, j = 0;
for(int i = 1; i <= m; i++){
scanf("%d", &y);
if(a[y]){ //看该数字是否在第一串数字中出现
b[j++] = a[y]; //将公共数字出现的序号存下来，所以后面最长上升子序列就是两串数字的公共子序列个数
}
}
//求b的上升子序列:
int len = 0, c[10005]={b[0]};
for(int i = 1; i < j; i++){
if(b[i] > c[len]){
c[++len] = b[i];
}
else{
int w = find(c, 0, len, b[i]);
c[w] = b[i];
}
}
printf("%d ", len + 1);
}
return 0;
}