問題概要

1 - 20 - 13 + 14 - 5

のような、 $N$ 個の正の整数を「+」「-」で連結した計算式が与えられる。この計算式に () を挿入する。たとえば、次のようにする。

$1−(20−(13+14)−5)=13$

計算結果の最大値を求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

基本的には、次のような DP をすればよさそうである。

dp[i][j]：最初の $i$ 個の整数を足し引きする。最後の数が $j$ 重のカッコの中にあるような場合についての、計算結果の最大値

まず、次のように単純化できる。

「+」の後には ( を入れないものとしてよい
「-」の後に '(' を入れるとき、2 個以上入れることはないものとしてよい

この単純化をしておくと、何重のカッコに入っているかによって、 $A_{i}$ を足すか引くかを特定可能になる。

さて、重要な考察として、以下のことがいえる。

カッコが 1 重の状態で、「-」が来たときは、そのままカッコを挿入せずに進むことで、カッコが 1 重のまま、 $A_{i}$ を足せる
カッコが 2 重の状態で、「-」が来たときは、一度 1 個のカッコを閉じてから、またカッコを 1 個挿入することで、カッコが 2 重のまま、 $A_{i}$ を足せる

特に、後者のことができることから、カッコを 3 重にする必要がないことが言える。つまり、 $j = 0, 1, 2$ のみ考えれば良い。よって、DP によって $O(N)$ の計算量で最適解が求められる。

最初は、一見すると、カッコを 2 重の状態からは、カッコをさらに挿入して 3 重にしなければ、 $A_{i}$ を足す状態にできないように思えたが、そんなことはなかった。この「カッコを 1 個閉じてから、また 1 個開く」という方法を見落としたことで、ずっと WA が出ていた。

#include <bits/stdc++.h>
using namespace std;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }


int main() {
    const long long INF = 1LL << 60;
    int N;
    cin >> N;
    vector<long long> A(N);
    cin >> A[0];
    for (int i = 1; i < N; i++) {
        char op;
        cin >> op;
        cin >> A[i];
        if (op == '-') A[i] *= -1;
    }

    // 0: 外, 1:　奇数重の括弧の中, 2: 偶数重の括弧の中
    vector dp(N+1, vector(3, -INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        long long add = abs(A[i]);
        
        if (A[i] > 0) {
            chmax(dp[i+1][0], dp[i][0] + add);  // そのまま
            chmax(dp[i+1][0], dp[i][1] + add);  // 1 個閉じる
            chmax(dp[i+1][1], dp[i][1] - add);  // そのまま
            chmax(dp[i+1][1], dp[i][2] - add);  // 1 個閉じる
            chmax(dp[i+1][2], dp[i][2] + add);  // そのまま
        } else {
            chmax(dp[i+1][1], dp[i][0] - add);  // 1 個開く

            chmax(dp[i+1][0], dp[i][1] - add);  // 閉じる
            chmax(dp[i+1][1], dp[i][1] + add);  // そのまま
            //chmax(dp[i+1][1], dp[i][1] - add);  // 1 個閉じて 1 個開く (不要)
            chmax(dp[i+1][2], dp[i][1] + add);  // さらに開く

            chmax(dp[i+1][0], dp[i][2] - add);  // 2 個閉じる
            chmax(dp[i+1][1], dp[i][2] + add);  // 1 個閉じる
            chmax(dp[i+1][2], dp[i][2] + add);  // 1 個閉じて 1 個開く
        }
    }
    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 066 E - Addition and Subtraction Hard (3D, 橙色, 900 点)

問題概要

制約

考えたこと