AOJ 2369 CatChecker
最近のんびり過ごしています。
解法
区間 dp をします。
dp[l][r] = (区間 [l, r) が猫の鳴き声文字列になっているか?)というのを判定します。
これは,
- s[l] = 'm', s[r-1] = 'w'
- s[m] = 'e' の時, dp[l+1][m-1], dp[m+1][r-1] も true
が成り立てば dp[l][r] も true です。
今回の場合は dfs で書いたほうが高速に処理できそうな気がしたのでメモ化再帰を使っています(メモ化再帰は関係ありそうなところしか dfs しないので)。
const int MAXN = 555; string s; int dp[MAXN][MAXN]; // [l, r) bool dfs(int l, int r) { int& ret = dp[l][r]; if (ret >= 0) return ret; if (r-l == 0) return ret = 1; if (s[l] != 'm' || s[r-1] != 'w') return ret = 0; ret = 0; for (int m = l+1; m < r-1; m++) { if (s[m] == 'e') { if (dfs(l+1, m) && dfs(m+1, r-1)) { return ret = 1; } } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> s; memset(dp, -1, sizeof(dp)); if (dfs(0, s.size())) cout << "Cat" << endl; else cout << "Rabbit" << endl; return 0; }