302852: CF552E. Vanya and Brackets

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

Vanya and Brackets

题意翻译

Vanya正在认真地做他的数学作业,他碰到了一个长度为N的序列,构成序列的元素都在1~9之间,并且各个元素由加号和等号构成了一个式子。 Vanya现在需要通过增加一组小括号来改变运算顺序(运算优先级,括号>乘法>加法)。 **输入格式:** 一个不带括号的式子。 **输出格式:** 加了一组小括号后该式子能达到的最大值。 **说明:** 其中式子元素个数小于等于5001。

题目描述

Vanya is doing his maths homework. He has an expression of form ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF552E/b8c6979b49468fd46854350f61bc168b56400c5a.png), where $ x_{1},x_{2},...,x_{n} $ are digits from $ 1 $ to $ 9 $ , and sign ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF552E/e24e10e0fe3325df5f4ed9d1a1ca93a7ed1327b9.png) represents either a plus '+' or the multiplication sign '\*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.

输入输出格式

输入格式


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.

输出格式


In the first line print the maximum possible value of an expression.

输入输出样例

输入样例 #1

3+5*7+8*4

输出样例 #1

303

输入样例 #2

2+3*5

输出样例 #2

25

输入样例 #3

3*4*5

输出样例 #3

60

说明

Note to the first sample test. $ 3+5*(7+8)*4=303 $ . Note to the second sample test. $ (2+3)*5=25 $ . Note to the third sample test. $ (3*4)*5=60 $ (also many other variants are valid, for instance, $ (3)*4*5=60 $ ).

Input

题意翻译

Vanya正在认真地做他的数学作业,他碰到了一个长度为N的序列,构成序列的元素都在1~9之间,并且各个元素由加号和等号构成了一个式子。 Vanya现在需要通过增加一组小括号来改变运算顺序(运算优先级,括号>乘法>加法)。 **输入格式:** 一个不带括号的式子。 **输出格式:** 加了一组小括号后该式子能达到的最大值。 **说明:** 其中式子元素个数小于等于5001。

加入题单

上一题 下一题 算法标签: