最长上升/公共子序列

LCS的输出：
一、对于 $O (n^{2})$ 暴力，记录一下子序列中，每个元素的前置元素，然后逆序得到答案。

二、对于 $O (n l o g n)$ 二分，要注意的是我们维护的递增序列只能得到最长上升子序列的值，而不一定能得到正确的子序列，因此要另寻他路。

/* 字典序最小的Lis Author: solego */
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010, INF = 1e10;
struct Elem{
    int e, pre, len;
}q[N];
int n, dis[N], now, ans[N];

void b_search_change(int t){
    int l = 1, r = now;
    while(l < r){
        int mid = l + r >> 1;
        if(q[dis[mid]].e < q[t].e) l = mid + 1;
        else r = mid;
    }
    
    if(q[dis[l]].e != q[t].e){
        q[t].pre = dis[l - 1];
        q[t].len = l;
        dis[l] = t;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &q[i].e);
    
    q[1].pre = INF; dis[0] = INF; dis[++now] = 1; 
    for(int i = 2; i <= n; i++){
        if(q[i].e > q[dis[now]].e){
            q[i].pre = dis[now];
            q[i].len = ++now;
            dis[now] = i;
        }
        else if(q[i].e < q[dis[now]].e){
            b_search_change(i);
        }
    }
    
    int Max_len = 0, pos = 1;
    for(int i = 1; i <= n; i++) {
        if(Max_len <= q[i].len){
            Max_len = q[i].len;
            pos = i;
        }
    }
    
    int g = 0; 
    for(int i = pos; i != INF; i = q[i].pre) ans[g++] = q[i].e;
    
    printf("Lis的长度：%d\n", Max_len);
    printf("Lis序列为：");
    for(int i = g - 1; i >= 0; i--) printf("%d%c", ans[i], " \n"[i == 0]);
    
    return 0;
}

/* Test case 1: 8 3 1 2 6 4 5 10 7 Test case 2: 8 1 4 7 2 5 9 10 3 case2是为了证明dis数组存储的不一定是真正的最长子序列。 */

普通版本的LCS

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010;
char A[N], B[N];
int f[N][N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", A + 1); scanf("%s", B + 1);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; 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]);
            
    printf("%d\n", f[n][m]);
    
    return 0;
}

部分序列可优化成 $O (n l o g n)$

/* nlogn输出LCS 注意当重复元素过多会退化成O(mnlog(mn)) 待优化细节：两个序列中以mn更小的为位置标准 */
#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 1e5 + 10;
int b[N], inv[N], n, g;
int ans[N], ga;

struct A{
	int v, pre;
}a[N];

struct Q{
	int v, num;
}q[N];

int b_s(int l, int r, int x) {
	while(l < r) {
		int mid = l + r >> 1;
		if(q[mid].v > x) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i].v);
	for(int i = 1; i <= n; i++) scanf("%d", &b[i]), inv[b[i]] = i; 
	
	//1.将a中的数用b数转换，2.求nlogn最长上升子序列的路径 
	for(int i = 1; i <= n; i++) a[i] = {inv[a[i].v], 0};
	
	q[g] = {0, 0};
	q[++g] = {a[1].v, 1};
	for(int i = 2; i <= n; i++) {
		if(a[i].v > q[g].v) {
			a[i].pre = q[g].num;
			q[++g] = {a[i].v, i};
		} 
		else if(a[i].v < q[g].v){
			int t = b_s(1, g, a[i].v);
			a[i].pre = q[t - 1].num;
			q[t] = {a[i].v, i};
		}
	}
	
	ans[++ga] = b[inv[q[g].v]];
	for(int i = a[q[g].num].pre; i; i = a[i].pre) ans[++ga] = b[inv[a[i].v]];
	
	printf("LCS长度：%d\n", g);
	printf("LCS序列："); 
	for(int i = ga; i >= 1; i--) printf("%d%c", ans[i], " \n"[i == 1]);
	 
	return 0;
}

由于对于重复元素过多的序列可能会退化到 $O (n m l o g (n m))$
故使用该方式的时候最好可以先考虑以哪个序列为参考修改另一个序列。

具体过程：分别预处理 $a$ 序列和 $b$ 序列中每个元素个数，
如对 $a$ 求取每个元素个数，然后计算在 $b$ 中形成的序列长度
与对 $b$ 求取每个元素个数，然后计算在 $a$ 中形成的序列长度
比较选择以哪个序列为参考。

普通版本的 $L C I S ： O (n m)$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010;
int a[N], b[N], n, m, T;
int f[N][N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
	
	for(int i = 1; i <= n; i++){ 
		int maxv = 1;
		for(int j = 1; j <= m; j++){
			f[i][j] = f[i][j - 1];
			if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
			if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
		}
	}
	
	int res = 0;
	for(int i = 1; i <= m; i++) res = max(res, f[n][i]);
	
		printf("%d\n", res);
	
	return 0;
}