AOJ 2369 - CatChecker

問題概要

文字列Sが与えられるので、それが "Cat" か "Rabbit" かを判定せよ。

ただし、文字列Sが "Cat"とは、
CAT := ””(empty string) | ’m’+CAT+’e’+CAT+’w’
を満たすことである。(+は連結を意味する)

文字列Sが"Cat"でなければ、"Rabbit"である。

制約

• 1 ≤ |S| ≤ 500
• 文字列Sの各文字は、'm', 'e', 'w' のいずれかである。

解法

区間DP。
dp[区間の左][区間の右] := true or false

empty stringは、区間の左をL, 右をRとすると、L > R となるときである。

コード

#include <bits/stdc++.h>

using namespace std;

#define MAX 514

string S;
int memo[MAX][MAX];

bool rec(int L,int R){
    int &res = memo[L][R];
    if(res != -1) return res;
    if(L > R) return 1;
    if(S[L] != 'm' || S[R] != 'w') return (res = 0);
    res = 0;
    for(int i = L+1 ; i < R ; i++){
        if(S[i] == 'e'){
            res = max(res,rec(L+1,i-1)&rec(i+1,R-1));
        }
    }
    return res;
}

int main(){
    cin >> S;
    memset(memo,-1,sizeof(memo));
    cout << (rec(0,S.size()-1) ? "Cat" : "Rabbit") << endl;
    return 0;
}