AOJ 2710 An Equation in a Mine

問題文

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

解法

区間DP（メモ化再帰）．
ある演算子に注目して，左と右に分けて，再帰的に処理していくとよい．
演算子が + であれば，左も右も最大値を取るようにすればよい．-であれば，左を最大に，右を最小にすればよい．
つまり，ある区間に対して最大値と最小値の両方が必要である．

気をつける必要があるのは，(n) のように，一つの数字だけを括弧で囲えないということ．たとえば 1 - (2 + 3 + 4) の場合，1つ目の + に注目すると "1 - (2" と "3 + 4)" に分かれる．左を更に分解すると "1" と "(2" になるが，"(2" はどうやっても条件を満たさないのでダメ．
つまり "1 + (2" とか "3) + 4" みたいな形になるような分解は不可能ということ．逆に，それ以外はいい感じにカッコを書けば可能．（例えば "(1 + 2" は一番右に")"を付け加えればOKなので，こういう場合はある演算子で分解する前に "1 + 2" も計算しておくようにすればいい．）
これに注意してメモ化再帰を書く．

計算量は O(N^3)．かな．

ソースコード

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

using P = pair<int, int>;

constexpr int INF = 1e9;

P memo[201][201];

P rec(int l, int r, string const& s) {
    P& res = memo[l][r];
    if(res != P{-INF, INF}) {
        return res;
    }
    if(l == r) {
        int v = s[l] - '0';
        return res = make_pair(v, v);
    }
    if(s[l] == '(' && r-l >= 3) {
        P p = rec(l+1, r, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    if(s[r] == ')' && r-l >= 3) {
        P p = rec(l, r-1, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    for(int i=l+1; i<r; ++i) {
        char op = s[i];
        if(op == '+' || op == '-') {
            P rl = rec(l, i-1, s);
            P rr = rec(i+1, r, s);
            if(op == '+') {
                res.first = max(res.first, rl.first + rr.first);
                res.second = min(res.second, rl.second + rr.second);
            } else {
                res.first = max(res.first, rl.first - rr.second);
                res.second = min(res.second, rl.second - rr.first);
            }
        }
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); ++i) {
        for(int j=0; j<s.size(); ++j) {
            memo[i][j] = make_pair(-INF, INF);
        }
    }
    cout << rec(0, s.size()-1, s).first << endl;
}