【东方oj题解】1893、1821、1822

1893 - 最长上升子序列LIS（2）

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入

第一行包含整数 N 。

第二行包含 N 个整数，表示完整序列。

#include <bits/stdc++.h>
using namespace std;
//dp:长度为i的LIS的最后一位最小值是多少
int a[100100],dp[100100];
int i,n,l,r,mid;


int main() {
//读入
	scanf("%d",&n);
	for(i =1; i<= n; i++) {
		scanf("%d",&a[i]);
	}
//边界
	dp[1]= a[1];
	int len=1;
//LIs的长度//从第2个数开始求解
	for(i =2; i <= n; i++) { //如果 a[i]比 dp 最后一位大,a[i]直接续上去,增加 LIS的长度
		if(a[i]> dp[len]) {
			len++;
			dp[len]= a[i];
		} else {
//二分查找到 dp数组中第1个>=a[i]的元素下标，替换(dp 数组一定是递增的)
			l = 1;
			r= len;
			while(l <= r) {
				mid=(l+r)/2;
				if(a[i]<= dp[mid])r=mid -1;
				else l=mid +1;
			}
//替换
			dp[l]= a[i];
		}
	}
	printf("%d",len);

	return 0;
}

1821 - 最长公共子序列(LCS)(1)

#include <bits/stdc++.h>
using namespace std;
/*
a[i]==b[j],方程:dp[i-1][j-1]+1
a[i]!=b[j],方程:max(dp[i][j-1],dp[i-1][j])*/
const int N=1010;//常量，表示数组大小
int a[N],b[N],dp[N][N];
int n,i,j;
int main() {
	cin>>n;
	for(i =1; i<= n; i++)cin>>a[i];
	for(i =1; i<= n; i++)cin>>b[i];
//递推
	for(i = 1; i<= n; i++) {
		for(j = 1; j<= n; j++) {
			if(a[i]== b[j])dp[i][j]= dp[i-1][j-1]+ 1;
			else dp[i][j]= max(dp[i-1][j],dp[i][j-1]);
		}
	}
	cout<<dp[n][n];



	return 0;
}

1822 - 最长公共子序列(LCS)(2)

#include <bits/stdc++.h>
using namespace std;
/*原理:
1、因为两个序列都是1~n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同;
2、通过c数组将b序列的数字在a序列中的位置求出;
3、如果b序列每个元素在a序列中的位置递增，说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCS;
4、从而就可以转变成求用来记录新的位置的c数组中的LIS。*/
const int N=100100;
int a[N],b[N],c[N],dp[N];
int n,i;

int main() {

	cin>>n;
	for(i=1; i<= n; i++) {
		scanf("%d",&a[i]);
		c[a[i]]=i;//求出a数组的每个数的位置
	}
	for(i =1; i<= n; i++)scanf("%d",&b[i]);
//求b数组的每个数在a数组的位置(c[b[i]])的 LIS
	dp[1]=c[b[1]];//边界
	int len = 1;
	int l,r,mid;//从第2个数开始讨论
	for(i =2; i<= n; i++) { //增加 LIS 的长度
		if(c[b[i]] > dp[len]) {
			len++;
			dp[len]= c[b[i]];
		} else {
			l = 1;
			r= len;
			while(l<= r) {
				mid=(l+r)/2;
				if(c[b[i]]<= dp[mid])r= mid - 1;
				else l=mid +1;
			}
			dp[l]= c[b[i]];
		}
	}
	cout<<len;
	return 0;
}