线性动归3--最长上升子序列（LIS）与最长公共子序列（LCS）

最长上升子序列（LIS）

例题1：小明爱拦截

小明的国家最近受到了来自B国的威胁，因为B国要发射导弹攻击小明的国家，为了拦截这些导弹，国家把这个任务分配给了小明，让他开发一套拦截系统。小明很快开发出了一套系统，但是这种导弹拦截系统有一个缺陷：虽然它拦截的第一发炮弹能够到达任意的高度，但是以后拦截每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
【输入】
第一行，输入雷达捕捉到的敌国导弹的数量k（1<=k<=100000），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
【输出】
输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
【数据范围】
对于10%的数据，1<= k<= 8
对于50%的数据，1<= k<= 2048
对于100%的数据，1<= k<= 100000
0<导弹高度≤200000。
【样例输入】
8
300 207 155 300 299 170 158 65
【样例输出】
6

【解法一：O(n²)】
状态表示：f[i]表示从第一个数字开始算，以a[i]结尾的最长上升子序列的长度。(以a[i]结尾的所有上升序列中属性为最大值的那一个)

状态计算：
(1)j∈(0,1,2,…,i-1), 在a[i] > a[j]时，
f[i] = max(f[i], f[j] + 1)。

(2)若前面没有比i小的，f[i]为1（自己为结尾）。

(3)最后在找f[i]的最大值。

时间复杂度：
O(n²),只能得部分分哦

#include<bits/stdc++.h>
using namespace std;
int a[2002];
int f[2002];
int main()
{
	int n;
	for(int i = 1;i<=n;i++)cin>>a[i];
	int ans = 1;// 找出所计算的f[i]之中的最大值，边算边找
	for(int i = 1;i<=t;i++)
	{
		f[i]=1;// 设f[i]默认为1，找不到前面数字小于自己的时候就为1
		
		for(int j = 1;j<i;j++)
			if(a[i]<a[j])//求下降，若求上升则为> 
				f[i]=max(f[i],f[j]+1);// 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
				
		ans = max(f[i],ans);//也可以使用下面注释的循环来求
	}
//	for(int i = 1;i<=n;i++)
//		ans = max(ans,f[i]);	
	cout<<ans<<endl;
	return  0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【解法二：O(nlogn)】
使用二分优化。
状态表示：1. 定义f[L] 表示到当前a[i] 为止，长度为L的递增子序列中，结尾数字的最小值。

可以想象，随着L的增大，f[L]的值也是递增的，不会存在长度为2 的递增子序列结尾数字大于长度为3 的递增子序列结尾数字。因为长度为3 的递增子序列就包括了长度为2 的递增子序列。

每加入一个新的数字a[i] ，对L 进行更新.L就是我们所求。
例如：5,1,6,8,2,4,5,10

#include <iostream>

using namespace std;

const int N = 1010;
int n, cnt;
int w[N], f[N];

int main() {
    cin >> n;
    for (int i = 0 ; i < n; i++) cin >> w[i];

    f[cnt++] = w[0];
    for (int i = 1; i < n; i++) {
        if (w[i] > f[cnt-1]) f[cnt++] = w[i];
        else {
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (f[mid] >= w[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = w[i];
        }
    }
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1 #include <bits/stdc++.h>
2 using namespace std;
3 const int MAXN = 100010;
4 int arr[MAXN], dp[MAXN]; //dp[i]表示长度为i+1的上升子序列的最小结尾
5
6 int LIS(int n){
7 int where, idx = 1;
8 dp[0] = arr[0];
9 for (int i = 1; i < n; i++) {
10 if (arr[i] <= dp[idx - 1])
11 dp[idx++] = arr[i];
12 else{
13 where = upper_bound(dp, dp + idx, arr[i], greater<int>()) - dp;
14 dp[where] = max(dp[where], arr[i]);
15 }
16 }
17 return idx;
18 }
19
20 int main(){
21 int n;
22 cin >> n;
23 for (int i = 0; i < n; i++)
24 cin >> arr[i];
25
26 memset(dp, 0, sizeof(dp));
27 cout << LIS(n) << endl;
28 return 0;
29 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

最长公共子序列（LCS）

例2：最长公共子序列

题目描述
给出 1,2,\ldots,n1,2,…,n 的两个排列 P1 和 P2 ，它们的最长公共子序列。
输入格式
第一行是一个数 n。
接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。
输出格式
一个数，即最长公共子序列的长度。
输入
5
3 2 1 4 5
1 2 3 4 5
输出
3
说明/提示
对于 50% 的数据，n≤10³ ；
对于 100% 的数据， n≤10⁵ 。

【解法一】
状态：设f[i][j]表示两个字符串走到i,j（a[]串走到i,b[]串走到j)位置时获得的最长的公共子序列的长度。

如果两个字符相等(a[i]==b[j])，就可以直接转移到f[i-1][j-1]，不相等的话，两个字符一定有一个可以抛弃，可以对f[i-1][j],f[i][j-1]两种状态取max来转移.

#include <iostream>
using namespace std;
const int N = 10010;
int n;
char a[N], b[N];
int f[N][N];
int main() {
  cin >> n;
  for(int i = 1;i<=n;i++) cin>>a[i];
  for(int i = 1;i<=n;i++) cin>>b[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i] == b[j]) {
        f[i][j] = f[i - 1][j - 1] + 1;
      } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  cout << f[n][n] << '\n';
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

会超时哦！
【解法二】
因为两个序列都是1~ n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个map数组将A序列的数字在B序列中的位置表示出来——

因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCS——那么就可以转变成nlogn求用来记录新的位置的map数组中的LIS。

#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}
	for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}
	int len=0;
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=len,mid;
		if(map[b[i]]>f[len])f[++len]=map[b[i]];
		else 
		{
		while(l<r)
		{	
		    mid=(l+r)/2;
		    if(f[mid]>map[b[i]])r=mid;
			else l=mid+1; 
		}
		f[l]=min(map[b[i]],f[l]);
     	}
    }
    cout<<len;
    return 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30