blog。显然答案为\(0\)不行。打表发现最优答案总为\(1\)。考虑构造取到\(1\)的下界。观察到，\(\text{LCS}\le1\)等价于去掉两序列都不存在的数后，两序列完全相反。于是有：在\(\{x\},\{y\}\)后增加两序列都不存在的数，不影响LCS。进行\(\{x\}\to\{a,x,b\},\{y\}\to\{b,