CodeForces - 552E Vanya and Brackets —— 加与乘运算的组合-白红宇

CodeForces - 552E Vanya and Brackets —— 加与乘运算的组合

阅读量：4954 次

发布时间：2019-06-12

本文共 2848 字，大约阅读时间需要 9 分钟。

题目链接：

Vanya is doing his maths homework. He has an expression of form $\text{[math]}$ , where x₁, x₂, ..., x_n are digits from 1 to 9, and sign $\text{[math]}$ 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.

Input

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.

Output

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

Examples

Input

3+5*7+8*4

Output

Input

2+3*5

Output

Input

3*4*5

Output

Note

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).

题意：

给出一个只有加法和乘法的算式，且数字的范围为1~9，算式里面没有括号。问：怎样加一对括号，使得算式的结果最大？

题解：

1.比划一下，可发现规律：括号加在两‘+’中间，最终结果没有改变；括号加在‘+’和‘*’之间，可使结果变大，但不一定最优。只有当括号加在两'*'之间时，结果是最大。

2.题目规定了‘*’不会超过15个，所以可直接枚举左右括号的放置位置，然后求出算式的值，取最大值即可。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 typedef long long LL;15 const double eps = 1e-8;16 const int INF = 2e9;17 const LL LNF = 9e18;18 const int MOD = 1e9+7;19 const int MAXN = 1e5+10;20 21 char a[10000];22 LL s[MAXN], len;23 int pos[MAXN];24 25 LL solve(int l, int r)26 {27 LL sum = 0, t1 = 1, t2 = 1, t3 = 1;28 int top = 0;29 30 if(2<=l) //左边31 {32 s[top++] = a[1]-'0';33 for(int i = 2; i<=l-2; i+=2)34 {35 if(a[i]=='*') s[top-1] = 1LL*s[top-1]*(a[i+1]-'0');36 else if(a[i]=='+') s[top++] = (a[i+1]-'0');37 }38 t1 = s[--top];39 while(top) sum += s[--top];40 }41 42 //中间：43 s[top++] = a[l+1]-'0';44 for(int i = l+2; i<=r-2; i+=2)45 {46 if(a[i]=='*') s[top-1] = 1LL*s[top-1]*(a[i+1]-'0');47 else if(a[i]=='+') s[top++] = (a[i+1]-'0');48 }49 t2 = 0;50 while(top) t2 += s[--top];51 52 // 右边：53 if(r<=len-1)54 {55 s[top++] = a[r+1]-'0';56 for(int i = r+2; i<=len-1; i+=2)57 {58 if(a[i]=='*') s[top-1] = 1LL*s[top-1]*(a[i+1]-'0');59 else if(a[i]=='+') s[top++] = (a[i+1]-'0');60 }61 while(top>1) sum += s[--top];62 t3 = s[--top];63 }64 sum += 1LL*t1*t2*t3;65 return sum;66 }67 68 int main()69 {70 while(scanf("%s",a+1)!=EOF)71 {72 int cnt = 0;73 pos[++cnt] = 0;74 len = strlen(a+1);75 for(int i = 1; i<=len; i++)76 if(a[i]=='*') pos[++cnt] = i;77 pos[++cnt] = len+1;78 79 LL sum = 0;80 for(int l = 1; l<=cnt; l++) //枚举左右括号81 for(int r = l+1; r<=cnt; r++)82 sum = max(sum, solve(pos[l], pos[r]));83 84 cout<
                  
                   <

View Code

转载于:https://www.cnblogs.com/DOLFAMINGO/p/8995343.html

你可能感兴趣的文章