Zhengrui 和梦熊都出了这个题说明质量很好
问题不难但是很有意思，记录一下。
description
给你两个排列 \(A, B\)，每次可以消除 \(A\) 或者 \(B\) 的第一个元素，如果两个排列第一个元素不同可以同时消除，问最小操作次数。
\(1 \le n \le 10^6\)。
solution
考虑朴素 DP \(f_{i, j}\) 表示第一个排列消除到第 \(i\) 个元素，第二个排列消除到第 \(j\) 个元素的最小操作次数，然后 \(O(1)\) 转移，不难发现时间复杂度 \(O(nm)\)。
但是我们发现，如果 \(|i - j| \ge 2\) 的情况下一定不优，因为我可以两个一起消掉再消掉一个达成该局面，于是我们设 \(f_{i, j}\) 第二维表示差值，此时我们的复杂度便是 \(O(n)\) 的了。
本题是差值 DP 好题，告诉我们碰到编辑距离型 DP 要多想差值。