题目描述

有两个长度为 $n$ 的排列 $A,B$ ,你每次可以进行三种操作:

  • 删除 A 的第一个元素 a
  • 删除 B 的第一个元素 b

删除 $A$ 的第一个元素 $a$ 和 $B$ 的第一个元素 $b$ ,要求 $a≠b$
求把 $A,B$ 都删光需要的最少操作次数。

思路

正解是一个神奇的 dp。稍加思索就会发现如果不是两个排列的第一个元素一样的时候直接同时删就好了,需要决策的只是一样的时候删除第一个排列的还是第二个排列的。

令 $f_i$ 表示在第一个元素值为 $a_i$ 的时候卡住以后删光所需的最小操作数,找到删除第一个排列和第二个排列的第一个元素之后会在哪里卡住就能计算了。

然鹅我比赛的时候写了一个看起来很多的暴搜,但是爆零了。。。于是我很不甘心地调(chao)试(xi)了一波,事实证明暴搜也是能过的鸭!

令 $T_{i,j}$ 为准备删 $a_i$ ,$b_j$ 需要的操作次数。那么从 1,1 开始,先贪心地向后删除不相等的两个元素,然后从 $T_{i,j+1}$ 和 $T_{i+1,j}$ 种选取最小的即可。时间复杂度玄学。

代码