LIS和LCS

LIS：最长上升子序列

参考：最长上升子序列 (LIS) 详解+例题模板 (全)-CSDN博客

B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态

O(N^2)

解法：线性DP（N <= 5000）

dp[i]： 以 i 结尾的最长上升子序列长度

每次遍历一个位置i，往之前的位置遍历，找到每一个能连接上的序列，保存dp[i]为找到的最大长度。

1）若要求最长不下降子序列，可将条件 a[i] > a[j]改为 a[i] >= a[j]

2）若要求最长下降子序列，即：将数组逆序排序，再求最长上升子序列

cin>>n;
for(int i = 0 ; i < n ; i ++){
    cin>>a[i];
}
for(int i = 1 ; i < n ; i ++){
    for(int j = i-1 ; j >= 0 ;j --){
        if(a[i] > a[j]){ //不下降：a[i] >= a[j]
            dp[i] = max(dp[i],dp[j] + 1);
            res = max(res,dp[i]);
        }
    }
}
cout<<res+1<<endl;

O(NlogN)

解法：二分+贪心 (N <= 1e6)

low[i]：所有长度为i的子序列的中最小的结尾值。

对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。

遍历a数组，并不断维护low数组，最后得到的cnt值，就是最长上升子序列的长度。

如果a[i]能接在当前最长的子序列的末尾上，即 a[i] > low[cnt]，更新low[++cnt]为a[i]；

否则，往回找到一个第>= a[i]的low[j]，替换为a[i]，维护low[j]为同长度序列的最小值。

int binarySearch(int l,int r,int x){
	//查找区间[l+1,r]
    //找到第一个 >= x 的位置
	while(l+1 != r){
		int mid = (l+r)/2;
		if(low[mid] < x){
			l = mid;
		}else{
			r = mid;
		}
	}
	return r;
}

int main(void){
	cin>>n;
	for(int i = 0 ; i < n ; i ++){
		cin>>a[i];
	}
	low[++cnt] = a[0];
	for(int i = 1 ; i < n ; i ++){
		if(a[i] > low[cnt]){
			low[++cnt] = a[i];
		}else{
			//int j = lower_bound(low+1,low+cnt+1,a[i]) - low;
            //不下降：int j = upper_bound(low+1,low+cnt+1,a[i]) - low;
			int j = binarySearch(0,cnt,a[i]);
			low[j] = a[i];
		}
	}
	cout<<cnt<<endl;
	return 0;
}

LCS：最长公共子序列

P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

O(N*M)

左右末端若相等，当前值 == 删去当前末端的最大长度 + 1

左右末端若不相等，必然其中一个是无效的

cin>>n>>m;
for(int i = 1 ; i <= n ; i ++) cin>>a[i];
for(int i = 1 ; i <= m ; i ++) cin>>b[i];
for(int i = 1 ; i <= n ; i ++){
    for(int j = 1 ; j <= m ; j ++){
        if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
    }
}
cout<<dp[n][m];

求LCS序列

vector<int > lcs;
void getLcs(){
	int i = n;
	int j = m;
	while(i&&j){
		if(a[i] == a[j]){
			lcs.push_back(a[i]);
			i--;j--;
		}else{
            // 舍去dp值较小的末端
			if(dp[i-1][j] > dp[i][j-1]) i--;
			else j--;
		}
	}
	reverse(lcs.begin(),lcs.end());
}

O(N*logN)

P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

==前提！！！若A和B数组中的元素是相同的元素的不同排列==，即A中每个元素都能在B中找到相同的元素，

此时，LCS问题可以转化为LIS问题。

首先，对于初始数组，

A: 3 2 1 4 5
B: 1 2 3 4 5

我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：

A: a b c d e
B: c b a d e

这样标号之后，LCS长度显然不会改变。

由 两个序列的子序列一定是A的子序列，且A是单调递增的，

可以得到：只要子序列在B中单调递增，它就是A的子序列。

所以求A和B的LCS，就是求B的LIS，因此完成转化。

int binarySearch(int l, int r, int x){
	while(l+1 != r){
		int mid = (l+r)/2;
		if(low[mid] <= x){
			l = mid;
		}else{
			r = mid;
		}
	}
	return r;
}

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		Hash[a[i]] = i;
	}
	for(int i = 1 ; i <= n ; i ++){
		cin>>b[i];
		b[i] = Hash[b[i]];
	}
	low[++cnt] = b[1];
	for(int i = 2 ; i <= n ; i ++){
		if(b[i] > low[cnt]){
			low[++cnt] = b[i];
		}else{
			int p = binarySearch(0, cnt, b[i]);
			low[p] = b[i];
		}
	}
	cout<<cnt;
	return 0;
}