#P2165. 纹样拼接

    ID: 1554 传统题 文件IO:lacquer 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高− 上传者: 标签>动态规划区间DP字符串合肥市蜀山区区赛初中组IO 读写2026

纹样拼接

本题需要文件读写

文件 IO 为:输入文件 lacquer.in,输出文件 lacquer.out。请使用上述文件名读入和输出。

问题描述

有一块长度为 nn 的漆板,上面刻有字符串 ss。其中一段连续的位置有金色标记,字符串 tt 用 1 表示有金色标记的位置,用 0 表示没有标记的位置;也可能没有任何金色标记。

需要从 ss 中选出若干段不重叠的连续子串,按它们在原串中出现的先后顺序拼接,并满足:

  1. 拼接得到的字符串是回文串,即从左往右读和从右往左读完全相同。
  2. 原串中所有有金色标记的位置,必须被同一段选中的子串完整覆盖。

请计算满足条件的最长回文串的长度。如果不存在满足条件的方案,输出 0。

输入格式

从文件 lacquer.in 中读入数据。

第一行输入一个整数 nn,表示漆板长度。

第二行输入一个长度为 nn 的字符串 ss,只包含小写英文字母。

第三行输入一个长度为 nn 的字符串 tt,只包含字符 0 和 1。保证所有 1 出现在一个连续区间内,也可能没有 1。

输出格式

输出到文件 lacquer.out 中。

输出一行一个整数,表示满足条件的最长回文串长度。

样例输入 1

4
abba
0000

样例输出 1

4

样例输入 2

6
abccba
011100

样例输出 2

6

样例输入 3

11
abcdxyedcba
01100000000

样例输出 3

9

样例输入 4

23
abcdefghijxyzjihgfedcba
00111000000000000000000

样例输出 4

21

样例输入 5

15
abcdeffedcbaxyz
000011110000000

样例输出 5

12

评测数据规模

对于所有数据,保证 1≤n≤50001\le n\le5000,∣s∣=∣t∣=n|s|=|t|=n,其余条件如输入格式所述。

每个测试点 55 分,各测试点附加限制如下。

测试点 n≤n\le
1∼21\sim2 1010
3∼63\sim6 100100
7∼107\sim10 500500
11∼1511\sim15 10001000
16∼2016\sim20 50005000