首页 > 代码库 > GDFZOJ 子序列

GDFZOJ 子序列

2024-08-17 10:46:45   219人阅读

题意：

给出两个字符串A,B，求出A，B的LCS，然后抽出A中长度为LCS的子序列，问有多少个也是B的子序列？

 

题解：

首先很显然肯定需要求出LCS。

现在考虑记录，

现在考虑定义：首先套路的根据答案来定义，定义状态sum[i][j]表示A串中前i个字符中，有多少个长度为dp[i][j]的子序列在B中前j个出现过。

现在考虑转移：如果dp[i][j] == dp[i-1][j]，那么sum[i][j] += sum[i-1][j] 表示不选第i个字符

现在考虑必选第i个字符，那么需要找到B串中最后一个等于A[i]的字符的位置pre，并且如果 dp[i - 1][pre - 1] + 1 == dp[i][j]，sum[i][j] += sum[i-1][pre-1]

 

代码：

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

const int N = 1e3 + 7;
const int mod = 1e9 + 7;
char ch1[N], ch2[N];
int dp[N][N], sum[N][N], n, m, pre[N];

int main () {
	gets(ch1 + 1), gets(ch2 + 1);
	n = strlen (ch1 + 1), m = strlen (ch2 + 1);
	for (int i = 0; i <= n; ++i) sum[i][0] = 1;
	for (int j = 0; j <= m; ++j) sum[0][j] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			dp[i][j] = max (dp[i - 1][j], dp[i][j - 1]);
			if (ch1[i] == ch2[j]) dp[i][j] = max (dp[i][j], dp[i - 1][j - 1] + 1);
		}
	}
	for (int j = 1; j <= m; ++j) {
		pre[ch2[j]] = j;
		for (int i = 1; i <= n; ++i) {
			if (dp[i - 1][j] == dp[i][j]) sum[i][j] = (sum[i][j] + sum[i - 1][j]) % mod;
			if (pre[ch1[i]] && dp[i - 1][pre[ch1[i]]-1] + 1 == dp[i][j]) {
				sum[i][j] = (sum[i][j] + sum[i - 1][pre[ch1[i]] - 1]) % mod;
			}
		}
	}
	cout << sum[n][m] << endl;
	return 0;
}

　　

总结：

这个题的基本条件是在LCS的基础上，首先dp出所有情况的LCS，然后再根据这个基础的dp再取计算方案数。

GDFZOJ 子序列


联系
我们