AT2273 [ARC066C] Addition and Subtraction Hard

· · 题解

性质：

  1. 括号都用在减号后。
  2. 减号后加括号除了这个减号和下一个减号之间的数减去，后面所有数都可加上绝对值，显然这个括号最优是右括号放在最后。

故枚举加括号的位置，前缀和优化即可。

时间复杂度 \mathcal O(n)。

#include<bits/stdc++.h>

using namespace std;

namespace Fread {
    const int SIZE = 1 << 23;
    char buf[SIZE], *S, *T;
    inline char getchar() {
        if (S == T) {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return '\n';
        }
        return *S++;
    }
}

namespace Fwrite {
    const int SIZE = 1 << 23;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush() {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c) {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct NTR {
        ~NTR() {
            flush();
        }
    } ztr;
}

#ifdef ONLINE_JUDGE
    #define getchar Fread::getchar
    #define putchar Fwrite::putchar
#endif

#define int long long

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int _ = 1e5 + 10;

int n, a, k, b[_], s[_], ss[_];

signed main() {
    n = read();
    b[1] = 0;
    for (int i = 1; i <= n; ++i) {
        if (i != 1) {
            char c = getchar();
            while (c != '+' && c != '-') c = getchar();
            if (c == '-') b[i] = 1, k++;
        }
        a = read();
        if (b[i] == 1) a = -a;
        s[i] = s[i - 1] + a;
        ss[i] = ss[i - 1] + abs(a);
    }
    int lst = n + 1;
    for (int i = 1; i <= n; ++i)
        if (b[i] == 1) {
            lst = i;
            break;
        }
    if (lst == n + 1 || k == 1)
        return printf("%lld", s[n]), 0;
    int ans = s[n];
    for (int i = lst + 1; i <= n; ++i)
        if (b[i] == 1)
            ans = max(ans, s[lst - 1] - (ss[i - 1] - ss[lst - 1]) + ss[n] - ss[i - 1]), lst = i;
    printf("%lld", ans);
    return 0;
}