ARC066 C: Addition and Subtraction Hard
在加减表达式中任意加括号使结果最大;只需要考虑减号后的括号,括号层数不超过两层,三状态 DP。来源 AtCoder ARC066 C · 标签 动态规划 / 括号 / 表达式 / 贪心
题目描述
给定只含加号和减号的表达式
可以在数字前或数字后插入任意多对括号,改变运算顺序,使表达式的值最大。求最大值。
,。
题解
只有减号后的括号有意义;加号后的括号可以直接去掉。进一步可以证明,嵌套括号最多只需要两层。
记 为处理前 项后,当前分别位于括号外、奇数层括号内、偶数层括号内的最大值。初始
处理第 项,运算符为 + 时:
- ;
- ;
- 。
运算符为 - 时:
- ;
- ;
- 。
答案为 。
状态中的奇偶层决定当前数前面的符号是否被括号翻转。两层已经足够:更多层括号可以通过调整括号闭合位置化简,不会得到更大的值。
复杂度
状态数为 ,每次转移常数次,时间为 。可以只保留上一层的三个状态,空间为 。