[JOI 2013 Final]搭乘 IOI 火车

[JOI 2013 Final]搭乘 IOI 火车

题意

给出两个由 \(\text{OI}\) 组成的字符串 \(S,T\)。

可以删除每个字符串的前缀和后缀。

每次从剩下部分的第一位取出一个字符放到新的字符串中。

要求新字符串必须以 \(\text{I}\) 开头结尾，相同的字符不能相邻，求新字符串的最大长度。

思路

定义 \(dp_{i,j,0/1,0/1}\) 表示考虑到 \(S\) 的第 \(i\) 位，\(T\) 的第 \(j\) 位，

已经没删完/删完了前缀，上一位填的是 \(\text{B}\)/\(\text{I}\)。

转移可用记忆化搜索的方式实现，好写好调。

注意数组开够以及初始化（如果当前为 \(\text{I}\) 则初始化为 \(0\)，否则为 \(-\infin\)）。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2005; // 数组要开到MAXN+1, 下面要访问

int n, m;
char S[N], T[N];
int dp[N][N][2][2];

int dfs(int Sx, int Tx, int b, int state) {
	if (Sx == n + 1 && Tx == m + 1) return (state == 1 ? 0 : -1e9);
	int &res = dp[Sx][Tx][b][state];
	if (res != -1) return res;
	res = (state == 1 ? 0 : -1e9); // 初始化
	if (!b) {
		if (Sx <= n) res = max(res, dfs(Sx + 1, Tx, 0, state));
		if (Tx <= m) res = max(res, dfs(Sx, Tx + 1, 0, state));
	}
	if (Sx <= n && state == 0 && S[Sx] == 'I') 
		res = max(res, dfs(Sx + 1, Tx, 1, 1) + 1);
	if (Sx <= n && state == 1 && S[Sx] == 'O') 
		res = max(res, dfs(Sx + 1, Tx, 1, 0) + 1);
	if (Tx <= m && state == 0 && T[Tx] == 'I')
		res = max(res, dfs(Sx, Tx + 1, 1, 1) + 1);
	if (Tx <= m && state == 1 && T[Tx] == 'O')
		res = max(res, dfs(Sx, Tx + 1, 1, 0) + 1);
	return res;
}

int main() {
	freopen("train.in", "r", stdin);
	freopen("train.out", "w", stdout); 
	
	memset(dp, -1, sizeof(dp));
	
	cin >> n >> m;
	scanf("%s%s", S + 1, T + 1);
	
	cout << max(0, dfs(1, 1, 0, 0))<< "\n";
	return 0;
}