AOJ 2680 LR

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2680

解法

メモ化再帰．memo[l][r] で，s[l..r]の取りうる最大値，もし無ければ "invalid" を入れていく．
完全に数字に置き換えられるならそうして(当然それが最適)，そうじゃないならLかRなので，カンマの位置を全探索して2つに分け，それらを再帰的にとくとよい．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
string memo[51][51];
 
string max(string const& a, string const& b) {
    if(a == "invalid") {
        return b;
    }
    if(a.size() > b.size()) {
        return a;
    } else if(a.size() < b.size()) {
        return b;
    } else {
        return (a < b ? b : a);
    }
}
 
string number(int l, int r, string const& s) {
    if(l < r && s[l] == '0') {
        return "invalid";
    }
    string res;
    for(int i=l; i<=r; ++i) {
        if(s[i] != '?' && !isdigit(s[i])) {
            return "invalid";
        }
        res += s[i] == '?' ? '9' : s[i];
    }
    return res;
}
 
string solve(int l, int r, string const& s) {
    string& res = memo[l][r];
    if(res != "") {
        return res;
    }
    res = number(l, r, s);
    if(res != "invalid") {
        return res;
    }
    if(s[l+1] != '(' && s[l+1] != '?') {
        return "invalid";
    }
    if(s[r] != ')' && s[r] != '?') {
        return "invalid";
    }
    for(int i=l+3; i<=r-2; ++i) {
        if(s[i] != ',' && s[i] != '?') {
            continue;
        }
        string l_max = solve(l+2, i-1, s),
               r_max = solve(i+1, r-1, s);
        if(l_max == "invalid" || r_max == "invalid") {
            continue;
        }
        if(s[l] == 'L' || s[l] == '?') {
            res = max(res, l_max);
        }
        if(s[l] == 'R' || s[l] == '?') {
            res = max(res, r_max);
        }
    }
    return res;
}
 
int main() {
    string s;
    cin >> s;
    cout << solve(0, s.size()-1, s) << endl;
}