题解：P15807 [JOI 2013 Final] 搭乘 IOI 火车 / Take the IOI train

Yuzih · 2026-05-08 12:18:52 · 题解

题目大意

有两种车厢 I 和 O，两个车库 S 和 T。刚开始车库中有若干车厢，我们可以先废弃掉两个车库中的一些车厢，之后按顺序从两个车库中取出车厢，组成列车。列车必须以 I 开头且以 I 结尾，中间任意两个相邻的车厢不能是同一个字母。求列车的最大长度。

分析

思路

• 列车的首尾必须为 I，且 I 和 O 交替出现。
• 可以将丢弃操作视为选择 S 的一个后缀 S[i\ldots M] 和 T 的一个后缀 T[j\ldots N] 作为可用的车厢序列。
• 在取车厢过程中，每次只需要关注当前需要取哪个字符（车厢），以及哪个车库当前能取到这个字符。
• 由于列车必须 I 开头 I 结尾，构造过程可以看作：选一个 I → 选一个 O → 选一个 I → … → 最后停在某个 I 上。

由此可以想到用动态规划解决此题。

状态设计

定义 f(i,j,k) 表示：当前 S 可用的第一个字符是 S_i（1\le i\le M），T 可用的第一个字符是 T_j（1\le j\le N），接下来需要的车厢类型为 k（k=1 表示需要 I，k=0 表示需要 O）时，继续拼接能获得的最大长度（包含即将取的这一节车厢）。

转移方程

当 k=1（需要 I）时：

• 可以从 S 取：若 i\le M 且 S_i = \texttt{I}，可以
  • 取完这个 I 后立即停止，获得长度 1；
  • 或者取完这个 I 后继续需要 O，获得长度 1 + f(i+1,\,j,\,0)；
  • 则该状态下的答案为二者的最大值，即 \max(1,\,1+f(i+1,j,0))。
• 可以从 T 取：若 j\le N 且 T_j = \texttt{I}，同理有
  • 停止得 1；
  • 继续得 1 + f(i,\,j+1,\,0)；
  • 答案同为二者的最大值，即 \max(1,\,1+f(i,j+1,0))。
• 若两处都无法取到 I，则 f(i,j,1)=0。

当 k=0（需要 O）时：

• 此时不能停止，因为结尾必须是 I。
• 从 S 取：若 i\le M 且 S_i = \texttt{O}，则必须继续需要 I，若后续合法，可获得 1 + f(i+1,\,j,\,1)。
• 从 T 取：若 j\le N 且 T_j = \texttt{O}，同样得 1 + f(i,\,j+1,\,1)。
• 若后续不合法（找不到 I），返回 0，当前状态也为 0。

边界处理：

• 在转移中若某侧已空（i>M 或 j>N），则对应 if 条件不成立，自然跳过。
• 若两侧都空（i>M 且 j>N），则对应 if 条件都不成立，跳过，返回 0。

提取答案

枚举所有可能的起点（即丢弃后剩余的后缀），对于每个 1\le i\le M 和 1\le j\le N，调用 f(i,j,1)，取最大值即为答案。

参考代码

AC 记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXSZ = 2010;

int n, m;
char s[MAXSZ], t[MAXSZ];
int dp[MAXSZ][MAXSZ][2];

int dfs(int i, int j, int k) {
    int ans = 0;
    if (dp[i][j][k] != -1) return dp[i][j][k];
    if (k == 1) {
        if (i <= n && s[i] == 'I') {
            int x = dfs(i + 1, j, 0);
            ans = max(ans, 1 + x);
        }
        if (j <= m && t[j] == 'I') {
            int x = dfs(i, j + 1, 0);
            ans = max(ans, 1 + x);
        }
    } else {
        if (i <= n && s[i] == 'O') {
            int x = dfs(i + 1, j, 1);
            if (x > 0) ans = max(ans, 1 + x);
        }
        if (j <= m && t[j] == 'O') {
            int x = dfs(i, j + 1, 1);
            if (x > 0) ans = max(ans, 1 + x);
        }
    }
    return dp[i][j][k] = ans;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= m; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dfs(i, j, 1));  // 由于第一项必须为 I，所以从需要找 I 的情况开始深搜。
        }
    }
    cout << ans;
    return 0;
}