AOJ 2680 LR
解法
メモ化再帰.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; }