Algebra Score [CodeChef ProCon 2018 C]

https://www.codechef.com/problems/PROC18D

N（≦200）個の数とN-1個の+,-演算子が順番に並んでいる。
適切に括弧をつけることで計算結果を最大化せよ。

前提知識

• 区間DP

考察過程

1. そもそもyukicoderで似た問題を見た これ
2. この問題の解法のエッセンスはmaxとminを持ってDPをするというところ
3. この問題もそのように取り組んでいこう
4. 括弧を作るとその部分がひとまとまりになる
5. 区間DPすればいいのでは？

解法

https://www.codechef.com/viewsolution/19758928

区間DPする。
rec(l,r) := [l,r]の区間の計算結果として得られる(最大値,最小値)
区間DPの中身は、l≦c＜rとなるcを全探索し、rec(l,c)とrec(c+1,r)を使って計算する。
メモ化でO(N^3)なので間に合う。

int N, A[202]; char O[202];
//---------------------------------------------------------------------------------------------------
int vis[202][202];
pair<ll, ll> memo[202][202];  // (max,min)
pair<ll, ll> rec(int l, int r) { // [l,r]
    if (vis[l][r]) return memo[l][r];
    vis[l][r] = 1;
 
    if (l == r) return memo[l][r] = { A[l], A[r] };
 
    pair<ll, ll> res = { -infl, infl };
    rep(c, l, r) { // [l,c], (c,r]
        auto x = rec(l, c);
        auto y = rec(c + 1, r);
 
        vector<ll> xx = { x.first, x.second };
        vector<ll> yy = { y.first, y.second };
 
 
        rep(i, 0, 2) rep(j, 0, 2) {
            if (O[c] == '+') {
                chmax(res.first, xx[i] + yy[j]);
                chmin(res.second, xx[i] + yy[j]);
            }
            else {
                chmax(res.first, xx[i] - yy[j]);
                chmin(res.second, xx[i] - yy[j]);
            }
        }
    }
 
    return memo[l][r] = res;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    cin >> A[0];
    rep(i, 1, N) cin >> O[i-1] >> A[i];
 
    rep(i, 0, N) rep(j, 0, N) vis[i][j] = 0;
    auto p = rec(0, N - 1);
    printf("%lld\n", p.first);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}