AOJ 2710 An Equation in a Mine

解法

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

気をつける必要があるのは,(n) のように,一つの数字だけを括弧で囲えないということ.たとえば 1 - (2 + 3 + 4) の場合,1つ目の + に注目すると "1 - (2" と "3 + 4)" に分かれる.左を更に分解すると "1" と "(2" になるが,"(2" はどうやっても条件を満たさないのでダメ.
これをもっと言い換えると,演算子で分解していって,最終的に全てが "1" や "2)" のような形になるなら,そういう分解は(いい感じに括弧を付け加えれば)可能であり,"(1" のような形がでてくればそのような分解は(どのように括弧を付け足しても)不可能であるということ.
これに注意してメモ化再帰を書けば良い.

計算量は 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;
}