会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
摘掉灯泡以后，两边留下的都是各自原来的子序列。两条子序列必须相同，记作 X，并且 X 里相邻字符不能相同。摘掉的只数是 ∣p∣+∣q∣−2∣X∣，所以只要把这种 X 尽量留长。
- 用 dp[i][j][c] 表示甲链的前 i 只、乙链的前 j 只里，以颜色 c 结尾时，最长交替公共序列的长度。c 取 R、G、B 三种。长度 0 表示还不存在以该颜色结尾的序列。
- 甲链第 i 只或乙链第 j 只被摘掉时，状态从 dp[i−1][j] 或 dp[i][j−1] 继承。
- 两只灯泡颜色相同，才可能同时留下。新序列可以只含这一只，长度是 1；也可以接在更短前缀里、以另一种颜色结尾的序列后面，长度再加 1。
- 三种结尾颜色里的最大值就是最长的 X。没有任何公共灯泡时，这个最大值是 0，答案就是两边长度之和。
