LIS+LCS+LCIS

时间：2024-04-18 16:35:31

PS:本篇博文均采用宏#define FOR(i, a, n) for(i = a; i <= n; ++i)

  • LIS：最长上升子序列

    废话不多说：http://baike.baidu.com/link?url=bRXFb18sGwPcKpplIIIq40hnngEUJe6S4b1PLgVnaby8zaahrO2NhI2tfoQZmw54#2_1 http://www.nocow.cn/index.php/%E6%9C%80%E9%95%BF%E4%B8%8D%E4%B8%8B%E9%99%8D%E5%AD%90%E5%BA%8F%E5%88%97

    设状态f(i)表示前i个数的最长上升子序列的长度，可以得到

    f(i) = max{f(j)} + 1, 其中 1 <= j < i且a[i] < a[j]

    答案就是max{f(i)}, 1<=i<=n

    CODE:

    FOR(i, 1, n) {
    
	f[i] = 1; //初始化
    
	FOR(j, 1, i-1)
    
		if(a[j] < a[i] && f[i] < f[j] + 1)
    
			f[i] = f[j] + 1, ans = max(ans, f[i]);
    
}

    其实就是在前面找一个k，接上去

    然后是带路径记录的LIS，想法是，既然每次都是找f[j]来接到f[i]上，那么记录每个j，然后逆着走即可：

    #include <cstdio>
    
using namespace std;
    
#define FOR(i, a, n) for(i = a; i <= n; ++i)

const int maxn = 5000;
    
int n, a[maxn], f[maxn], i, j, ans;
    
int pre[maxn], path[maxn], pos, len;

void setIO() {
    
	freopen("in", "r", stdin);
    
	freopen("out", "w", stdout);
    
}
    
int main() {
    
	setIO();
    
	scanf("%d", &n);
    
	FOR(i, 1, n) scanf("%d", &a[i]);
    
	FOR(i, 1, n) {
    
		f[i] = 1; //初始化
    
		FOR(j, 1, i-1) //增序得出来答案是lower_bound(i)的。。
    
			if(a[j] < a[i] && f[i] < f[j] + 1) {
    
				f[i] = f[j] + 1;
    
				pre[i] = j; //记录接入的路径
    
				if(ans < f[i])
    
					ans = f[i], pos = i; //记录最长的开始下标
    
		}
    
	}
    
	printf("%d\n", ans);
    
	len = ans;
    
	if(ans > 0) path[ans--] = pos; //先加入进去，因为没有记录最后的接入路径
    
	while(ans && pos) {
    
		if(pre[pos] > 0) {
    
			path[ans--] = pre[pos];
    
			pos = pre[pos];
    
		}
    
	}
    
	FOR(i, 1, len) printf("%d ", a[path[i]]);
    
	return 0;
    
}
  • LCS：最长公共子序列

    还是去看nocow把：http://www.nocow.cn/index.php/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97

    设f(i, j)表示a的前i个数和b的前j个数的最大公共子序列长度，有

    f(i, j) = f(i-1, j-1) + 1,  a[i] == b[j]

    f(i, j) = max{f(i-1, j), f(i, j-1)},  a[i] != b[j]

    答案是f(sa, sb)，sa,sb是a和b的长度

    将这个用矩阵表示好理解，具体看nocow

    二维：

    FOR(i, 1, sa) FOR(j, 1, sb)
    
	if(seq1[i] == seq2[j]) f[i][j] = f[i-1][j-1] + 1;
    
	else f[i][j] = max(f[i-1][j], f[i][j-1]);

    由于是方程严格递增并且方程阶段是第二维，那么我们可以转化为一维的

    一维：

    FOR(i, 1, sa) FOR(j, 1, sb)
    
	if(seq1[i] == seq2[j]) f[j] = f[j-1] + 1;
    
	else f[j] = max(f[j], f[j-1]);

    那么用二维的我们还能求路径，与LIS不同的是，LCS求路径是方程的逆，逆回去即可。。。

    可以用矩阵来想

    for(i = sa, j = sb; j > 0 && i > 0;) {
    
	if(seq1[i] == seq2[j]) {
    
		path[num++] = seq1[i];
    
		i--; j--;
    
	}
    
	else (f[i-1][j] > f[i][j-1]) ? i-- : j--;
    
}

    全套：

    #include <cstdio>
    
#include <iostream>
    
using namespace std;
    
#define FOR(i, a, n) for(i = a; i <= n; ++i)

void setIO() {
    
	freopen("in", "r", stdin);
    
	freopen("out", "w", stdout);
    
}
    
const int maxn = 500;
    
int i, j, num, f[maxn][maxn], seq1[maxn], seq2[maxn], sa, sb;
    
int path[maxn];

int max(const int& a, const int& b) { return a < b ? b : a; }

int main() {
    
	setIO();

	scanf("%d%d", &sa, &sb);
    
	FOR(i, 1, sa) scanf("%d", &seq1[i]);
    
	FOR(i, 1, sb) scanf("%d", &seq2[i]);
    
	FOR(i, 1, sa) FOR(j, 1, sb)
    
		if(seq1[i] == seq2[j]) f[i][j] = f[i-1][j-1] + 1;
    
		else f[i][j] = max(f[i-1][j], f[i][j-1]);
    
	for(i = sa, j = sb; j > 0 && i > 0;) {
    
		if(seq1[i] == seq2[j]) {
    
			path[num++] = seq1[i];
    
			i--; j--;
    
		}
    
		else (f[i-1][j] > f[i][j-1]) ? i-- : j--;
    
	}
    
	cout << f[sa][sb] << endl;
    
	for(i = num-1; i >= 0; --i) cout << path[i] << ' ';
    
	cout << endl;
    
	return 0;
    
}
  • LCIS：最长公共上升子序列

    这个可以说是LCS和LIS的结合体~。我们用LIS的思想来想，3维的方法我不会。。网上也没有找到，那就只有用n^2算法把。。

    具体定义什么的可以参考前一篇博文

    这里更新一下求路径的以及一些注释

    #include <iostream>
    
#include <cstdio>
    
using namespace std;

#define FOR(i, a, n) for(i = a; i <= n; ++i)

void setIO() {
    
	freopen("in", "r", stdin);
    
	freopen("out", "w", stdout);
    
}
    
const int maxn = 550;
    
int seq1[maxn], seq2[maxn], sa, sb;
    
int f[maxn], pre[maxn][maxn], path[maxn], ans, len, maxi, temp, pos1, pos2, i, j, k;
    
int max(const int& a, const int& b) { return a < b ? b : a; }

int main() {
    
	setIO();

	cin >> sa >> sb;
    
	FOR(i, 1, sa) cin >> seq1[i];
    
	FOR(i, 1, sb) cin >> seq2[i];
    
	ans = 0;
    
	FOR(i, 1, sa) {
    
		maxi = temp = 0; //初始化，很重要
    
		FOR(j, 1, sb) //求lcds将a[i] > b[j]改为a[i] < b[j]即可
    
			if(seq1[i] > seq2[j] && f[j] > maxi) maxi = f[j], temp = j; //得到temp = max{f[i-1][k]}
    
			else if(seq1[i] == seq2[j]) {
    
				f[j] = maxi + 1;
    
				pre[i][j] = temp; //能接上b[j]的b[temp]，以后用答案直接索引到temp
    
				if(ans < f[j]) {
    
					pos1 = i; //记录最长公共上升seq所对应的下标i和j
    
					pos2 = j;
    
					ans = f[j];
    
				}
    
			}
    
	}
    
	cout << ans << endl;
    
	len = ans;
    
	//和LIS的路径几乎一模一样
    
	if(ans > 0) path[ans--] = pos2; //将最后的添上
    
	while(ans && pos1 && pos2) { //依据pos2（最长seq的j值）一直找
    
		if(pre[pos1][pos2] > 0) {
    
			path[ans--] = pre[pos1][pos2];  //将这些k记录下来
    
			pos2 = pre[pos1][pos2]; //更新接上的最大
    
		}
    
		pos1--; //因为要的是max{f[i-1][k]}，所以要倒着i-1回去找，即f[i-1][k]，记录的k值
    
	}
    
	FOR(i, 1, len) cout << seq2[path[i]] << ' ';
    
	cout << endl;

	return 0;
    
}

相关文章