第12回日本情報オリンピック 本選 「IOI列車で行こう(Take the 'IOI' train)」

普通にDPだった。
"""IOI列車は闇"""とだけ昔から聞いて怖いなーと思ったけど割と普通に通ってしまった。
闇要素どこにあるんだろう・・・

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

int n,m,ans;
int s[2004],t[2004];
int dp[2004][2004][2];

int han(int x){
	if(x == 0){
		return 1;
	}else{
		return 0;
	}
}

int main(){
	scanf("%d%d",&n,&m);
	char a[2003],b[2003];
	scanf("%s\n%s",a,b);
	for(int i = 1;i <= n;i++){
		if(a[i-1] == 'O'){
			s[i] = 1;
		}else{
			s[i] = 0;
		}
	}
	for(int i = 1;i <= m;i++){
		if(b[i-1] == 'O'){
			t[i] = 1;
		}else{
			t[i] = 0;
		}
	}
	for(int i = 1;i <= n;i++){
		if(s[i] == 0 || dp[i-1][0][0] != 0){
			dp[i][0][s[i]] = max(dp[i][0][s[i]],dp[i-1][0][han(s[i])]+1);
		}
	}
	for(int j = 1;j <= m;j++){
		if(t[j] == 0 || dp[0][j-1][0] != 0){
			dp[0][j][t[j]] = max(dp[0][j][t[j]],dp[0][j-1][han(t[j])]+1);
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(s[i] == 0 || dp[i-1][j][0] != 0){
				dp[i][j][s[i]] = max(dp[i][j][s[i]],dp[i-1][j][han(s[i])]+1);
			}
			if(t[j] == 0 || dp[i][j-1][0] != 0){
				dp[i][j][t[j]] = max(dp[i][j][t[j]],dp[i][j-1][han(t[j])]+1);
			}
			ans = max(ans,dp[i][j][0]);
		}
	}
	printf("%d\n",ans);
	return 0;
}