题面

gym102759G LCS 8

给定一字符串 \(S\)。求有多少不同的长度为 \(T\)，使得 \(|S| = |T|\)，且 \(S\) 和 \(T\) 的最长公共子序列长度大于等于 \(n-k\)。所有字符都为大写字母。

数据范围：\(1 \le |S| \le 5 \times 10^4, 0 \le k \le 3\)

题解

（下文令 \(n = |S|\)）

我们是如何 dp 求 \(lcs\) 的？

记录 \(a_{i, j}\) 表示 \(S\) 的前 \(i\) 个字符 和 \(T\) 的前 \(j\) 个字符的 \(lcs\) 。有 \(a_{i, j} = \max(a_{i - 1, j}, a_{i, j - 1}, a_{i - 1, j - 1} + [a_i = b_j])\)

如果我们对于每一个 \(T\) 中的位置 \(j\)，记录对于所有 \(i\)， \(lcs(i, j)\) 是多少。但是这样状态数过多，对于每一个位置 \(j\) 都有 \(n^n\) 个。

用一个常见的差分套路，记录 \(lcs(i, j) - lcs(i - 1, j)\)，这个值只有 \(0\) 和 \(1\)，这样状态数减少到 \(2^n\)。

我们发现 \(lcs(i, j) \le \min(i, j)\)，而由这个点对 \((i, j)\) 更新的 \(lcs(S, T)\) 不超过 \(lcs(i, j) + \min(n - i, n - j)\)。

如果 \(\min(i, j) + \min(n - i, n - j) \ge n - k\)，\((i, j)\) 这个点对才可能对答案有贡献。化简一下得到 \(\max(i, j) - \min(i, j) \le k\) 。所以我们记录满足 \(|i - j| \le k\) 的状态即可。

再记录一下 \(lcs(i, i)\)，状态数变成了 \((k + 1) 2^{2k}\)。

转移很简单，枚举 \(T_j\) 是哪一个字符，然后更新最长公共子序列的状态就可以了。

时间复杂度垃圾，是 \(\Theta(26nk^22^{2k})\)。空间复杂度 \(\Theta(nk 2^{2k})\) ,可以滚动数组优化到 \(\Theta(k 2^{2k})\)

被卡常了，加了个类似记忆化的东西就过了。

CF578D 是这题的弱化版，把 \(m\) 改为 \(1\)，字符集改一改就过了。

代码

gym102759G：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int n, m, now[N], nxt[N], ans;
int dp[N][1 << 7][5]; 
bool mp[256];
char s[N]; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> (s + 1) >> m, n = strlen(s + 1);
	if(m == 0) return cout << "1\n", 0;
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		memset(mp, 0, sizeof(mp));
		for(int j = max(i - m, 1); j <= min(i + m, n); j++) mp[s[j]] = 1;
		
		for(int j = 0; j < (1 << (m << 1)); j++) {
			for(int k = 0; k <= m; k++) if(dp[i - 1][j][k]) { 
				now[i - 1] = i - 1 - k;
				for(int t = 0; t < m; t++) now[i + t] = now[i + t - 1] + (j >> (t + m) & 1);
				for(int t = 1; t <= m; t++) if(i - 1 - t > 0) now[i - 1 - t] = now[i - t] - (j >> (m - t) & 1);
				int to1 = -1, to2;
				for(char t_i = 'A'; t_i <= 'Z'; t_i++) {
					if(!mp[t_i] && ~to1) {
						(dp[i][to1][to2] += dp[i - 1][j][k]) %= mod;
						continue;
					}
					int msk = 0;
					for(int wz = max(i - m, 1); wz <= i + m; wz++) 
						nxt[wz] = max(max(now[wz], now[wz - 1] + (s[wz] == t_i)), nxt[wz - 1]);
					for(int wz = max(i - m, 0); wz <= i + m - 1; wz++) if(nxt[wz] ^ nxt[wz + 1]) msk |= (1 << (wz - i + m));
					(dp[i][msk][i - nxt[i]] += dp[i - 1][j][k]) %= mod;
					if(!mp[t_i]) to1 = msk, to2 = i - nxt[i];
				}
			}
		}
	}
	for(int i = 0; i < (1 << (m << 1)); i++) for(int j = 0; j <= m; j++) (ans += dp[n][i][j]) %= mod;
	cout << ans << "\n";
	return 0;
} 

CF578D：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 7;
int n, S, now[N], nxt[N];
ll dp[N][4][3], ans; 
bool mp[26];
char s[N]; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> S, cin >> (s + 1);
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		memset(mp, 0, sizeof(mp));
		for(int j = max(i - 1, 1); j <= min(i + 1, n); j++) mp[s[j] - 'a'] = 1;
		for(int j = 0; j < 4; j++) {
			for(int k = 0; k <= 1; k++) if(dp[i - 1][j][k]) { 
				now[i - 1] = i - 1 - k, now[i] = now[i - 1] + (j >> 1 & 1);
				if(i - 2 > 0) now[i - 2] = now[i - 1] - (j & 1); 
				int to1 = -1, to2;
				for(char t_i = 'a'; t_i <= 'a' + S - 1; t_i++) {
					if(!mp[t_i - 'a'] && ~to1) {
						dp[i][to1][to2] += dp[i - 1][j][k];
						continue;
					}
					int msk = 0;
					for(int wz = max(i - 1, 1); wz <= i + 1; wz++) nxt[wz] = max(max(now[wz], now[wz - 1] + (s[wz] == t_i)), nxt[wz - 1]);
					for(int wz = max(i - 1, 0); wz <= i; wz++) if(nxt[wz] ^ nxt[wz + 1]) msk |= (1 << (wz - i + 1));
					dp[i][msk][i - nxt[i]] += dp[i - 1][j][k];
					if(!mp[t_i - 'a']) to1 = msk, to2 = i - nxt[i];
				}
			}
		}
	}
	for(int i = 0; i < 4; i++) ans += dp[n][i][1];
	cout << ans << "\n";
	return 0;
} 

祝大家学习愉快！