← 返回题目列表

AtCoder · joi2013ho2

2. 乘坐“IOI”列车

中文机器翻译题面 查看原题

配点: 100 点

在 IOI 国,这次新建了铁路。IOI 国行驶的列车是由若干车厢连接而成的,车厢中 I,O 的 2 每个车厢只能与不同种类关系的车厢连接。此外,为了在铁路上设置驾驶室,列车两端的车厢是种类 I 。假设一列火车由一串代表车辆类型的字符串按顺序连接表示,火车的长度就是该字符串的长度。例如, 当按照 IOIOI 的顺序连接车辆时,长度 5 可以组织火车,可以组织车辆 I 是单独的长度 这是 1 火车。车辆 OIOI 呀 即使您按照 IOOI 之类的顺序排列火车,也无法组织火车。

一些车辆 2 它存放在两个车库中。每个车库内,车辆都排成一排。编组时,车辆从车辆段取出并在车辆段前连接。只有距离车库入口最近的车辆才能被带出车库,但车辆的取出顺序是自由的。

在形成火车之前,您可以根据需要从车库取出任意数量的车厢,并将它们移动到另一条候车轨道上。一旦车辆被移动到候车轨道上,以后就不能再用来组成火车了。此外,一旦火车组装完毕,在组装完成之前,不可能将车辆从车辆段移至等待轨道。

编组列车时,无需使用车辆段内的所有车厢。换句话说,列车组装完毕后,车段内是否还有未使用的车辆也没有关系。

由于认为IOI国家乘坐火车的人数较多,因此我们希望尽可能长时间地组织火车。

列車を編成している途中であり,このとき車庫にある車両を待機用レールに移すことはできない.この図は入出力例 <var>1</var> に対応している.

課題

编写一个程序,根据仓库中存储的车辆信息,计算可以形成的火车的最大长度。每个车库存放的车辆行数是 2 字符类型 由仅由 I,O 组成的字符串表示,2 每个车库信息都有长度 M 字符串 S 和长度 它被给出为 N 字符串 T 。每个字母 1 代表一辆车,其字符与车型相同。字符串的 1 第一个字母代表距离车库入口最近的车辆,最后一个字母代表车库内最远的车辆。

制限

1 \leqq M \leqq 2\,000  文字列 S 长度
1 \leqq N \leqq 2\,000  文字列 T 长度

入力

从标准输入读取以下数据。

  • 1 在线 写在方格 M, N 用空格分隔。
  • 2 行是一个字符串 写入 S 。
  • 3 行是一个字符串 写入 T 。

出力

表示可组装火车最大长度的整数被发送到标准输出。 输出为 1 行。火车 1 如果您无法组织 输出0 。

採点基準

评分数据中,分配的分数 20 对于%,M \leqq 10,N \leqq 10 满意。 设

评分数据中,分配的分数 50 对于%,M \leqq 50,N \leqq 50 满意。 设


入力例 1

5 5
OIOOI
OOIOI

出力例 1

7

S 代表的车库为车库S,并且 设T 代表的车库为车库T。此时,例如第一个 1 车辆,从车库 T 出发 2 将车辆取出等待后,如果按车库S、车库S、车库T、车库S、车库S、车库T、车库T的顺序取出车辆,则长度 7 火车 IOIOIOI 可以组织。

此外,第一个 1 车辆,从车库 T 出发 2 取出车辆并等待后,您还可以按以下顺序取出车辆:车库T、车库T、车库S、车库S、车库T、车库S、车库S。 7 火车可以组装。不可能组织比这更长的火车。 输出 7 。


入力例 2

5 9
IIIII
IIIIIIIII

出力例 2

1

1 仅由一辆车组成的火车 请注意, I 也满足成为火车的条件。