$Jerry$Jerry

$正解部分$正解部分

• 首先可以将所有相邻的正数合并在一起, 不影响答案, 且会使得数列具有性质 $1$1: 加号之后一定是减号 .
• 还有个非常重要的性质 $2$2: 若两个 负号 同时出现在一起, 则除第一个负号后的数字, 后面的所有数字均可取到正值 .

考虑从后往前去决定每个数前加不加括号,

1. $A\left[i\right]\>0$A[i]>0, 括号对其无影响, $F\left[i\right]=A\left[i\right]+F[i+1]$F[i]=A[i]+F[i+1]
2. $A\left[i\right]\&lt;0$A[i]<0,
   1. $A[i+1]\&lt;0$A[i+1]<0, 根据性质 $2$2, $F\left[i\right]=A\left[i\right]+suf\_sum[i+1]$F[i]=A[i]+suf_sum[i+1] .
   2. $A[i+1]\&gt;0$A[i+1]>0, 根据性质 $1$1, 有两个决策, 分别是
      1. 不加括号得到 $A[i+1]$A[i+1],
      2. 加括号失去 $A[i+1]$A[i+1]但得到 $i+2$i+2后所有数字的和;
         得到 $F\left[i\right]=\max \left(A\right[i]+F[i+1],A[i]-A[i+1]+suf\_sum[i+2\left]\right)$F[i]=max(A[i]+F[i+1],A[i]−A[i+1]+suf_sum[i+2])

$实现部分$实现部分

• 多组数据, $cnt$cnt 初值 $0$0 , $suf\_sum[cnt+1]=0$suf_sum[cnt+1]=0
• 注意 $suf\_sum\left[\right]$suf_sum[] 处理时需要对 $A\left[i\right]$A[i] 加绝对值 .
• $abs\left(\right)$abs()函数会炸 $int$int .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 2e5 + 10;

int N;
int cnt;
int A[maxn];

ll B[maxn];
ll F[maxn];
ll suf_sum[maxn];

char opt[3];

ll abd(ll x){ return x>0?x:-x; }

void Work(){
        N = read();
        A[1] = read();
        for(reg int i = 2; i <= N; i ++){
                scanf("%s", opt);
                A[i] = read();
                if(opt[0] == '-') A[i] = -A[i];
        }
        cnt = 0;
        for(reg int i = 1; i <= N; i ++){
                B[++ cnt] = A[i];
                while(i != N && A[i] >= 0 && A[i+1] >= 0) B[cnt] += A[++ i];
        }
        suf_sum[cnt+1] = 0;
        for(reg int i = cnt; i >= 1; i --) suf_sum[i] = suf_sum[i+1] + abd(B[i]);
        F[cnt] = B[cnt];
        for(reg int i = cnt-1; i >= 1; i --){
                if(B[i] >= 0) F[i] = B[i] + F[i+1];
                else if(B[i+1] >= 0) F[i] = std::max(B[i]+F[i+1], B[i]-B[i+1]+suf_sum[i+2]);
                else F[i] = B[i] + suf_sum[i+1];
        }
        printf("%lld\n", F[1]);
}

int main(){
        int T_ = read();
        while(T_ --) Work();
        return 0;
}