第3题-甲乙指示灯链

会员专享

请先登录，登录后可使用今日免费解锁；开通会员后可解锁完整内容。

开通会员

解题思路

摘掉灯泡以后，两边留下的都是各自原来的子序列。两条子序列必须相同，记作 $X$ ，并且 $X$ 里相邻字符不能相同。摘掉的只数是 $|p|+|q|-2|X|$ ，所以只要把这种 $X$ 尽量留长。

用 $dp[i][j][c]$ 表示甲链的前 $i$ 只、乙链的前 $j$ 只里，以颜色 $c$ 结尾时，最长交替公共序列的长度。 $c$ 取 $\mathrm{R}$ 、 $\mathrm{G}$ 、 $\mathrm{B}$ 三种。长度 $0$ 表示还不存在以该颜色结尾的序列。
甲链第 $i$ 只或乙链第 $j$ 只被摘掉时，状态从 $dp[i-1][j]$ 或 $dp[i][j-1]$ 继承。
两只灯泡颜色相同，才可能同时留下。新序列可以只含这一只，长度是 $1$ ；也可以接在更短前缀里、以另一种颜色结尾的序列后面，长度再加 $1$ 。
三种结尾颜色里的最大值就是最长的 $X$ 。没有任何公共灯泡时，这个最大值是 $0$ ，答案就是两边长度之和。

车间并列挂着甲、乙两条指示灯链。每条链由若干只灯泡串成，每只灯泡只亮红、绿、蓝中的一种，分别记作 $\mathrm{R}$ 、 $\mathrm{G}$ 、 $\mathrm{B}$ 。

可以摘掉任意灯泡。摘掉之后，它左右两边的灯泡会靠拢接上，原有的先后次序不变。收工时两条链留下的颜色序列必须一模一样，并且序列里紧挨着的两只灯泡不能同色。

请算出最少一共要摘掉多少只灯泡。若两边都摘空，两条空链视为相同，也视为满足相邻不同色。

仅一行，两个由大写字母组成的字符串 $q$ 和 $p$ ，中间用一个空格分开。 $q$ 是乙链， $p$ 是甲链。

两个字符串只含 $\mathrm{R}$ 、 $\mathrm{G}$ 、 $\mathrm{B}$ 。

$1 \le |q|,|p| \le 2000$

只写出一个整数，表示最少摘掉的灯泡只数。

输入

RBRG RGBG

输出

说明

甲链 $\mathrm{RGBG}$ 摘掉第二只，剩下 $\mathrm{RBG}$ 。乙链 $\mathrm{RBRG}$ 摘掉第三只，剩下 $\mathrm{RBG}$ 。 $\mathrm{RBG}$ 中相邻颜色都不一样。两边各摘一只，总数是 $2$ 。

输入

GB GB

输出

说明

两条链本来就是 $\mathrm{GB}$ ，彼此相同，相邻颜色也不同，不用摘。

输入

BBB GGG

输出

说明

乙链全是 $\mathrm{B}$ ，甲链全是 $\mathrm{G}$ ，没有任何一只灯泡能同时留在两边。六只都要摘掉。

选择提交后点击「开始AI分析」