「JOI 2013 Final」搭乘 IOI 火车 题解

题目大意

有两个字符串 $S$ 和 $T$，分别代表两个车库中的车厢序列。每个字符是 I 或 O。

火车合法条件：

• 火车两端必须是 I
• 相邻车厢必须不同（即 I 后面必须是 O，O 后面必须是 I）

操作规则：

1. 组装前可以丢弃任意数量的车厢（从字符串开头丢弃）
2. 组装时，可以从两个车库的剩余部分轮流取车厢
3. 目标是构造最长的合法火车

算法思路

关键观察

合法的火车形如：IOIOI...OI 或 IOIO...IOI，即交替的 I 和 O，且两端是 I。

由于两端必须是 I，所以火车长度一定是奇数。

动态规划定义

定义状态： $dp[i][j][v]$ 表示已经使用了 $S$ 的前 $i$ 个字符和 $T$ 的前 $j$ 个字符，且当前最后一个字符的类型是 $v$（0表示'O'，1表示'I'）时，能组成的最大火车长度。

状态转移方程

对于每个状态 $(i, j, v)$，有两种选择：

1. 从 $S$ 取下一个字符：

   • 如果 $s[i+1]$ 匹配当前需要的字符类型 $v$，则可以接上
   • 转移：$dp[i+1][j][v] = \max(dp[i+1][j][v], \max(v, dp[i][j][v \oplus 1] + 1))$

2. 从 $T$ 取下一个字符：

   • 如果 $t[j+1]$ 匹配当前需要的字符类型 $v$，则可以接上
   • 转移：$dp[i][j+1][v] = \max(dp[i][j+1][v], \max(v, dp[i][j][v \oplus 1] + 1))$

其中 $\max(v, ...)$ 处理了从空序列开始的情况。

初始化与答案

• 所有状态初始化为 $-\infty$
• 最终答案是所有 $dp[i][j][1]$ 中的最大值（因为火车必须以 I 结尾）

代码实现

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

inline char Q(const int &val) {
    return val & 1 ? 'O' : 'I';  // 0->'O', 1->'I'
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    string s, t;
    cin >> s >> t;
    s = ' ' + s;  // 转为1-indexed
    t = ' ' + t;
    
    // dp[i][j][v]: 使用S前i个，T前j个，最后字符类型为v时的最大长度
    vector<vector<array<int, 2>>> dp(n + 1, vector<array<int, 2>>(m + 1, {-inf, -inf}));

    // 动态规划
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i != n) {
                int v = (s[i + 1] == 'O' ? 0 : 1);  // 下一个字符的类型
                // 两种情况：从空序列开始，或从已有序列接上
                dp[i + 1][j][v] = max(dp[i + 1][j][v], max(v, dp[i][j][v ^ 1] + 1));
            }
            
            if (j != m) {
                int v = (t[j + 1] == 'O' ? 0 : 1);  // 下一个字符的类型
                // 两种情况：从空序列开始，或从已有序列接上
                dp[i][j + 1][v] = max(dp[i][j + 1][v], max(v, dp[i][j][v ^ 1] + 1));
            }
        }
    }

    int ans = 0;
    // 找所有以'I'结尾的序列的最大长度
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            ans = max(ans, dp[i][j][1]);
        }
    }

    printf("%d\n", ans);
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \times m)$，其中 $n$ 和 $m$ 是两个字符串的长度
• 空间复杂度：$O(n \times m)$

样例验证

样例1：

输入：
5 5
OIOOI
OOIOI

输出：
7

程序找到的最优解是长度为7的火车 IOIOIOI，符合预期。

样例2：

输入：
5 9
IIIII
IIIIIIIII

输出：
1

只能组成长度为1的火车 I，符合预期。