ARC066 C: Addition and Subtraction Hard

在加减表达式中任意加括号使结果最大;只需要考虑减号后的括号,括号层数不超过两层,三状态 DP。

来源 AtCoder ARC066 C · 标签 动态规划 / 括号 / 表达式 / 贪心

题目描述

给定只含加号和减号的表达式

𝐴1op1𝐴2…op𝑁−1𝐴𝑁.

可以在数字前或数字后插入任意多对括号,改变运算顺序,使表达式的值最大。求最大值。

1≤𝑁≤105,1≤𝐴𝑖≤109。

题解

只有减号后的括号有意义;加号后的括号可以直接去掉。进一步可以证明,嵌套括号最多只需要两层。

记 𝑓𝑖,0,𝑓𝑖,1,𝑓𝑖,2 为处理前 𝑖 项后,当前分别位于括号外、奇数层括号内、偶数层括号内的最大值。初始

𝑓1,0=𝐴1,𝑓1,1=𝑓1,2=−∞.

处理第 𝑖 项,运算符为 + 时:

  • 𝑓𝑖,0=max(𝑓𝑖−1,0,𝑓𝑖−1,1,𝑓𝑖−1,2)+𝐴𝑖;
  • 𝑓𝑖,1=𝑓𝑖−1,1−𝐴𝑖;
  • 𝑓𝑖,2=𝑓𝑖−1,2+𝐴𝑖。

运算符为 - 时:

  • 𝑓𝑖,0=−∞;
  • 𝑓𝑖,1=max(𝑓𝑖−1,0,𝑓𝑖−1,1)−𝐴𝑖;
  • 𝑓𝑖,2=max(𝑓𝑖−1,2,𝑓𝑖−1,1)+𝐴𝑖。

答案为 max(𝑓𝑁,0,𝑓𝑁,1,𝑓𝑁,2)。

状态中的奇偶层决定当前数前面的符号是否被括号翻转。两层已经足够:更多层括号可以通过调整括号闭合位置化简,不会得到更大的值。

复杂度

状态数为 3𝑁,每次转移常数次,时间为 𝑂(𝑁)。可以只保留上一层的三个状态,空间为 𝑂(1)。

参考

源码位置