[DP记录]AT2273 [ARC066C] Addition and Subtraction Hard

**题意** ： 给出一个只包含 $+,-,$ 正整数的式子。 在式子中添加一些括号，使运算结果最大，输出最大的结果。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 显然，在加号后填括号是无用的。 考虑最外层的一对括号里的东西。我们需要最小化内部的贡献。 对于前缀的一些 $+$ ，贡献无法取反。 在第一个 $-$ 后面的所有数，可以通过适当地加括号使得贡献都是负的。 于是，我们枚举最外层左括号的位置（显然右括号最好填在最右），然后计算贡献即可。 （注意，不加括号也是一种方案） 复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; int n,a[MaxN]; ll s[MaxN],s2[MaxN]; char op[MaxN]; int main() { scanf("%d",&n); op[1]='+';scanf("%d",&a[1]); for (int i=2;i<=n;i++) scanf("%s%d",&op[i],&a[i]); for (int i=1;i<=n;i++){ s[i]=s[i-1]+a[i]; s2[i]=s2[i-1]+(op[i]=='+' ? a[i] : -a[i]); } ll ans=s2[n]; for (int i=n,las=n+1;i;i--) if (op[i]=='-'){ ans=max(ans,s2[i-1]-(s[las-1]-s[i-1])+s[n]-s[las-1]); las=i; } printf("%lld",ans); return 0; } ```