Jerry [动态规划]

$Jerry$

---

$color{red}{正解部分}$

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

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

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

---

$color{red}{实现部分}$

• 多组数据, $cnt$ 初值 $0$ , $suf\_sum[cnt+1] = 0$
• 注意 $suf\_sum[]$ 处理时需要对 $A[i]$ 加绝对值 .
• $abs()$函数会炸 $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
", F[1]);
}

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