CFR 552 E. Vanya and Brackets ( Greedy, Expression Parsing, Python )
題意:
給一個由 '+', '*', '0' ~ '9' 組成的合法數式,要求在任意合法的位置插入一對括弧,求最大可能結果。
資料規模:
The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs + and * .
The number of signs * doesn't exceed 15.
解法:
首先注意到乘法的數量不超過 15 個。
考慮貪心,假設當前一個左端在括弧內,下一個符號是加,接著才是乘。那麼可以大略這樣想:左端當前的和是 s,要考慮是否納入括弧內的值為 v,在後面的乘法待乘的是 x。如果不將 v 納入括弧內,得到的結果是 s + v * x。反之如果納入,則會得到 ( s + v ) * x。顯然,由於數據範圍只有 [ 1, 9 ],所以在遇見乘號之前,加號都不斷納入,一定不會比較差。這麼一來就有結論,只需檢查左界和右界都為乘法的情形。用 python 的 eval() 函數水過。
時間 / 空間複雜度:
O( 15^2 * | S | ) / O( | S | )
S = input() ans = 0 for ll in range( len( S ) ): if not ( ll == 0 or S[ ll - 1 ] == '*' ): continue for rr in range( ll + 1, len( S ) + 1, 1 ): if not ( rr == len( S ) or S[ rr ] == '*' ): continue ans = max( ans, eval( S[ : ll ] + "(" + S[ ll : rr ] + ")" + S[ rr : ] ) ) print( ans )