[题目传送]
[思路] 运用小学生的直觉，我们只能加一个括号，那么这个括号加的位置肯定要将“和”最大的一边，和乘法相结合，才可能有更好的结果。
例如：
原式：1+2+3*4+3*9
我们应该觉得括号加在这几个位置需要考虑就行：
(1+2+3)*4+3*9
(1+2+3*4+3)*9
1+2+3*(4+3)*9
1+2+3*(4+3*9)
加在其他位置并不能影响结果，所以观察发现，其实我们只要盯住乘号，就能枚举所有情况。
好的，以上是小学生思路，来讲讲大学生思路，既然这题长度最多50，数字1-9。那我们把每个可能的位置都加一遍，看看哪种比较好不就好了么！（才50的长度，不会超时的）
这里处理算式可以用两个数组，和一个栈来处理讨厌的＋和＊的优先级问题
我们把读进来的算式，数字和运算符号分别放在两个数组里比如上面例子 1+2+3*4+3*9
分解成
A[] : 1 2 3 4 3 9
B[] : + + * + *
然后我们用一个数组模拟栈，比如它叫做 S[]
进行以下操作：
1.把A[0] 元素压进栈，S[0] = A[0];
2.循环B数组,如果B[i] 是 ＋ 号，将 A[i+1] 加进S[] 数组中，如果是＊号，将S[]数组的最后一个元素取出，乘上A[i + 1] 再压回去到S[] 的末尾。
经过这样的处理后S[]变成了 S[] : 1 2 12 27
把S[] 数组求个和就是原式的值啦～！
接下来用两个套嵌的for循环来枚举所有的括号出现的位置，左括号，右括号。
我们约定，l , r 分别是两个括号的位置，表示左括号出现在下标为l的数的左边，有括号出现在下标为r的数的右边。
计算括号加在l ，r位置的函数叫做Get(l,r)；
我们可以先Get(0,0) 让表达式的值按不加括号的顺序先计算初始值。
Get(0,0) 等同于(1)+2+3*4+3*9 可以看出来相当于没有加上括号。接下来的任务基本就是枚举l r的位置，然后计算Get就行，既然前面计算过不加括号的值作为初始值，我们枚举的时候注意 r - l >= 1这样括号就不会只扩在一个数上了。
接下来写Get(l,r)函数，我们先计算l - r这一段被括号扩起来的算式，按照前面那种“一个栈两个数组的方式” 计算出了这个括号内的值为val。
然后我们算整个算式的值，我们在碰到 左括号 之前，还是按照“一个栈两个数组”的方式计算值，也就是 0 － l 。
碰到 l 时，特别判断下，将val放进去操作。 然后 l － r 位置都不进行操作。
最后 r － 最后一个数字，仍然正常操作。
最后把栈里的数字加起来，就得到了括号加在l r位置的算式值了，返回到主函数里，比较下，输出就行。
[代码]
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 vector num; 8 vector oper; 9 10 void init(){11 num.clear(); oper.clear();12 return ;13 }14 15 void check(){16 for(int i = 0 ; i < num.size() ; i++) cout << num[i] << " " ; cout << endl;17 for(int i = 0 ; i < oper.size() ; i++) cout << oper[i] << " "; cout << endl;18 return ;19 }20 21 long long Get(int l , int r){22 stack in;23 for(int i = l ; i <= r ; i++){24 if(i == l) in.push(num[i]);25 else{26 if(oper[i - 1] == '+') in.push(num[i]);27 else{28 long long temp = in.top();29 in.pop();30 in.push(temp * num[i]);31 }32 }33 }34 long long val = 0;35 while(!in.empty()){36 val += in.top(); in.pop();37 }38 /////39 vector temp_num;40 vector temp_op;41 for(int i = 0 ; i < num.size() ; i++){42 if(i == l){temp_num.push_back(val); continue;}43 if(i >= l && i <= r) continue;44 temp_num.push_back(num[i]);45 }46 for(int i = 0 ; i < oper.size() ; i++){47 if(i >= l && i < r) continue;48 temp_op.push_back(oper[i]);49 }50 ///check51 //cout << "IN " << l << " " << r << endl;52 //for(int i = 0 ; i < temp_num.size() ; i++) cout << temp_num[i] << " "; cout << endl;53 //for(int i = 0 ; i < temp_op.size() ; i++) cout << temp_op[i] << " "; cout << endl;54 ////55 long long ans = 0;56 in.push(temp_num[0]);57 for(int i = 0 ; i < temp_op.size() ; i++){58 if(temp_op[i] == '+') in.push(temp_num[i + 1]);59 else{60 long long temp = in.top(); in.pop();61 in.push(temp * temp_num[i + 1]);62 }63 }64 while(!in.empty()){65 ans += in.top();66 in.pop();67 }68 //cout << "OUT " << ans << endl;69 return ans;70 }71 int main(){72 string in;73 while(cin >> in){74 init();75 int size = in.size();76 for(int i = 0 ; i < size ; i++){77 if(i%2 == 0) num.push_back(in[i] - '0');78 else oper.push_back(in[i]);79 }80 long long ans = Get(0,0);81 for(int i = 0 ; i < num.size() - 1 ; i++){82 for(int j = i + 1 ; j < num.size() ; j++){83 ans = max(ans , Get(i,j));84 }85 }86 cout << ans << endl;87 }88 return 0;89 }