专栏文章

[动态规划] 离线区间 LCS

FFelix72
算法·理论参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minqvo8j
此快照首次捕获于
2025/12/02 06:52
3 个月前
此快照最后确认于
2025/12/02 06:52
3 个月前
查看原文

概括

有字符串 s,ts, t 长度为 n,mn, m，现有 kk 组无特殊性质的区间询问，则该离线区间 LCS\text{LCS} 问题可以在 O((k+nlog⁡n)m)O((k + n\log n)m) 时间内解决。

正文

某天，桑格莉娅在又一次被三跑之后很红温，她找到同为版本角色的麦克莫顿，询问他怎样提升追击能力。
麦克略加思索，说到：“多看职业联赛。”
桑格莉娅觉得好有道理啊，于是找了一份 IVL\text{IVL} 赛场上的的歌剧演员集锦拿出来看。看着看着她发现了自己的问题：庄园里很多地方是她可以用技能直接一步跳过去的，而她却不太会估计距离，导致多走了很多弯路。
比如下面的这个图，假设右下角有个人在修机子，桑格莉娅要从左上角赶到右下角，她本可以走红色的最短路，但是由于对地图不熟悉，她最终走的可能是蓝色的较劣路径。
了解这一点后，她开始研究最短路径怎么计算。一旁凑热闹的艾维告诉她，这个问题可以用 DP\text{DP} 求解，设 fi,jf_{i, j} 表示走到当前格子时经过的最多斜边数量就可以啦。
桑格莉娅表示你说的对，但是我想要一个子矩阵查询的算法，O(n2log⁡n)O(n^2\log n) 的那种。
众人犯了难。询问的自由度太高了，让人不知从何下手。但是很快猫猫教会的安表示，自己教派有一种叫做猫树的宗教仪式，大概就是把一个问题分治，每次解决跨过中点的询问，剩下的再递归，这样，只要保证问题的两半可以合并，那就能用一个 log⁡n\log n 直接让问题减少一个维度，太赚了。
于是现在需要解决的问题就变成了这样：从点 (1,i)(1, i) 到 (k,j)(k, j)，最多走几条斜边？可是这个问题还是有三个维度，最好能用数据结构或者性质再去掉一维。
经过漫长的手玩，观察力惊人的桑格莉娅观察到了一个性质！
她说：“当 i,j,ki, j, k 确定时，可以设我经过的斜边数量最多为 ww。显然当 kk 增大 11 时，ww 有可能加一，也有可能不变。但是我发现，对于一个固定的 jj 来说，ii 越小，ww 越可能加一。”
“为什么呢？如果 (1,i)→(k,j)(1, i) \to (k, j) 的答案可以加一的话，那么一定存在一条像这样的蓝色路径，使得我可以走 k→k+1k \to k + 1 行的一条斜边。那么这个问题可以分两种情况讨论。”
“如果 (1,i−1)→(k,j)(1, i - 1) \to (k, j) 的答案本就等于 (1,i)→(k,j)(1, i) \to (k, j) 的答案，那么可以先一步走到 (1,i)(1, i) 再走蓝色路径；”
“另一种情况是 (1,i−1)→(k,j)(1, i - 1) \to (k, j) 的答案比 (1,i)→(k,j)(1, i) \to (k, j) 的答案大 11。但是你看，这 (1,i)→(k,j)(1, i) \to (k, j) 的最优路径不可能和蓝色路径交错过去，不然交错之后的后半段直接走蓝色就可以了对不对？”
“因此我们可以知道，k→k+1k \to k + 1 时对于固定的 jj，有一个前缀的 ii 会满足 (1,i)→(k,j)(1, i) \to (k, j) 的答案加一，我们把这个前缀的右端点记为 q(k+1,j)q(k + 1, j)。”
“不仅如此啊，j→j+1j \to j + 1 时对于固定的 kk，有一个后缀的 ii 会满足 (1,i)→(k,j)(1, i) \to (k, j) 的答案加一，剩下的不变，不妨记这个后缀的左端点为 p(k,j+1)p(k, j + 1)。证明也可以用这个格子图。”
艾维看了看感觉挺对的。“但是我们还是不能回答 (1,i)→(k,j)(1, i) \to (k, j) 的答案啊？除非把 pp 和 qq 都算出来 …\dots 欸欸欸好像真能算啊？”
桑格莉娅和艾维发现，pp 和 qq 好像能递推！具体是怎么个事呢？她们举了个例子帮你理解：
当 j,kj, k 固定时，ans(i,j,k)ans(i, j, k) 是一个以 ii 作为下标的数列。设其为 a1,a2,…,ana_1, a_2, \dots, a_n。那么根据刚才研究的前后缀理论，有以下三种情况可以讨论。为了便于你理解，设 n=7n = 7：

Case 1

假设 (j−1,k−1)→(j,k)(j - 1, k - 1) \to (j, k) 没有斜边，且 q(j−1,k)<p(j,k−1)q(j - 1, k) < p(j, k - 1)：
ans(i,j−1,k−1):a1,a2,a3,a4,a5,a6,a7ans(i, j - 1, k - 1) : a_1, a_2, a_3, a_4, a_5, a_6, a_7；
ans(i,j−1,k):a1+1,a2+1,a3,a4,a5,a6,a7ans(i, j - 1, k) : a_1 + 1, a_2 + 1, a_3, a_4, a_5, a_6, a_7；
ans(i,j,k−1):a1,a2,a3,a4,a5+1,a6+1,a7+1ans(i, j, k - 1) : a_1, a_2, a_3, a_4, a_5 + 1, a_6 + 1, a_7 + 1；
则我们可知 ans(i,j,k)=max⁡(ans(i,j−1,k),ans(i,j,k−1))ans(i, j, k) = \max(ans(i, j - 1, k), ans(i, j, k - 1))。有：
ans(i,j,k−1):a1+1,a2+1,a3,a4,a5+1,a6+1,a7+1ans(i, j, k - 1) : a_1 + 1, a_2 + 1, a_3, a_4, a_5 + 1, a_6 + 1, a_7 + 1；
欸嘿，正好 pp 和 qq 都不变。

Case 2

假设 (j−1,k−1)→(j,k)(j - 1, k - 1) \to (j, k) 没有斜边，且 q(j−1,k)<p(j,k−1)q(j - 1, k) < p(j, k - 1)；
（读者自写不难）

Case 3

假设 (j−1,k−1)→(j,k)(j - 1, k - 1) \to (j, k) 有斜边，那娅娅自然是直接跳过去啦。
（读者自写不难）
讨论完这三种情况，桑格莉娅很快写出了一下封装的 DP\text{DP}：
CPP
struct Table
{
	char s[N], t[N]; int n, m, p[N][N], q[N][N];
	inline void reset() {n = m = 0;}
	inline void get_s(char c) {s[++n] = c;}
	inline void get_t(char c) {t[++m] = c;}
	inline void debug()
	{
		cerr << "s -> "; for(int i = 1; i <= n; ++i) cerr << s[i]; cerr << '\n';
		cerr << "t -> "; for(int i = 1; i <= m; ++i) cerr << t[i]; cerr << '\n';
		cerr << "Matrix P : \n";
		for(int i = 0; i <= m; ++i)
		{
			for(int j = 0; j <= n; ++j)
				cerr << p[i][j] << " ";
			cerr << '\n';
		}
		cerr << "Matrix Q : \n";
		for(int i = 0; i <= m; ++i)
		{
			for(int j = 0; j <= n; ++j)
				cerr << q[i][j] << " ";
			cerr << '\n';
		}
	}
	inline void work()
	{
		for(int i = 0; i <= m; ++i) p[i][0] = i + 1;
		for(int i = 0; i <= n; ++i) q[0][i] = 0;
		for(int i = 1; i <= n; ++i)
		{
			for(int j = 1; j <= m; ++j)
			{
				if(s[i] != t[j] && q[j - 1][i] < p[j][i - 1])
					p[j][i] = p[j][i - 1], q[j][i] = q[j - 1][i];
				else p[j][i] = q[j - 1][i] + 1, q[j][i] = p[j][i - 1] - 1;
			}
		}
//		debug();
	}
};
只要传进 ss 和 tt 两个串，她就能用这个表格计算出 pp 和 qq。
CPP
inline void work(int l, int r, vector < Query > tmp)
{
	if(tmp.empty()) return ;
	if(l == r)
	{
		for(Query qy : tmp)
		{
			for(int i = qy.t_l; i <= qy.t_r; ++i)
				if(s[qy.s_l] == t[i])
					res[qy.id] = 1;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	
	Tl.reset(), Tr.reset();
	for(int i = mid; i >= l; --i) Tl.get_s(s[i]);
	for(int i = m; i >= 1; --i) Tl.get_t(t[i]);
	for(int i = mid + 1; i <= r; ++i) Tr.get_s(s[i]);
	for(int i = 1; i <= m; ++i) Tr.get_t(t[i]);
	Tl.work(), Tr.work();
	
	vector < Query > tmp_l, tmp_r;
	for(Query qy : tmp)
	{
		if(qy.s_r <= mid) tmp_l.push_back(qy);
		else if(mid < qy.s_l) tmp_r.push_back(qy);
		else
		{
			memset(wl, 0, sizeof(wl));
			memset(wr, 0, sizeof(wr));
			for(int i = 1; i <= qy.t_r; ++i)
			{
				int l = Tr.p[i][qy.s_r - mid], r = i;
				++wr[l], --wr[r + 1];
			}
			for(int i = 1; i <= m + 1; ++i) wr[i] += wr[i - 1];
			for(int i = m; i >= qy.t_l; --i)
			{
				int l = Tl.p[m - i + 1][mid - qy.s_l + 1], r = m - i + 1;
				++wl[l], --wl[r + 1];
			}
			for(int i = 1; i <= m + 1; ++i) wl[i] += wl[i - 1];
			
			int cur = 0;
			for(int i = qy.t_l - 1; i <= qy.t_r; ++i)
				cur = max(cur, wl[m - i + 1] + wr[i + 1]);
			res[qy.id] = cur;
		}
	}
	
	work(l, mid, tmp_l), work(mid + 1, r, tmp_r);
}
很快，基于猫树的程序主体也写出来了。
艾维还是有些不解：“你的询问是如何处理的呢？”娅娅解释道：“一次询问 (ls,rs,lt,rt)(l_s, r_s, l_t, r_t) 可以被拆成 (ls,mid,lt,p)(l_s, mid, l_t, p) 和 (mid+1,rs,p+1,rt)(mid + 1, r_s, p + 1, r_t) 的和的最大值。我们自己枚举这个 pp，只要提前用差分-前缀和思想预处理一下，那么就可以 O(1)O(1) 回答两小半的答案啦。”
解决了这个问题，桑格莉娅很高兴，打算开着自己新写的这个自动路径规划挂打一把排位。
不久之后，众人听到准备间的一声怒吼：“谁把我歌剧演员 ban 了？！”
（完）

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...