飞机票：http://codeforces.com/contest/552/problem/E

题意：给你个没有括号的正确表达式，其中只包含*和+，和1~9的数字，添加一个括号，使得最后的数字最大。

分析：假设一共有n个数字，其实就是在选择两个标i和j(i<=j)使得1~i-1和i~j和j+1~n的计算最大。具体可以维护前缀和后缀，具体需要维护哪些值，前缀的话，假设从1~i,我们维护这个值的大小，但是还不够，因为我们不知道紧接的是*还是+,如何是+的话还是很好处理的，只要把两个相加就好了，如果是乘，我们还得维护1~i最后一个+后面的数字的大小，因为我们要把它与后面的数字相乘然后后缀也是一样的，维护相同的值，不一样的是方向相反，因为我们如果从前面开始，后缀就没办法维护了。具体求数组的方法是使用栈来求(这里就不细讲，是每个人应该会的)假设我们已经求的前缀的和li和前缀要维护最右边的数字lvali 和后缀的和ri和维护最左边的值rvali，接下来就是枚举需要加括号的地方。假设为在i前面加和在j后面加。则有

求的前缀到i-1的值为 ls，后缀到j+1的值为rs，且lval为v1 ，rval为v2，中间的i到j的结果为s。

(1)如果i前面的符号是*和j后面的符号是*,则大小sum就为ls+rs-v1-v2+v1*s*v2

因为v1和v2要和s乘为新的数，所以要减去。

(2)如果只有i前面的符号是*,则大小sum为ls-v1+v1*s+rs;

因为后面的话是直接加上去的。

(3)如果只有j+1后面的符号为*，则跟(2)差不多性质

(4)如果i从1开始，则只要考虑rs的情况

(5)如果j到了n,则只要考虑ls的情况

复杂度为O（n*n）然后啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5678;
char ch[maxn];
int  ai[maxn];
int  bi[maxn];
int len;
LL lr[2][maxn];
LL limit[2][maxn];

int st;
void get()
{
    for(int i=0; i<2; i++)
    {
        int s=1;
        int c=1;
        int cz=-1;
        if(i==1)
        {
            s=st;
            c=-1;
            cz=0;
        }
        lr[i][s]=ai[s];
        vector<LL> V;
        LL sum=ai[s];
        V.push_back(ai[s]);
        limit[i][s]=ai[s];
        for(int j=1; j<st; j++)
        {
            s=s+c;
            if(bi[s+cz]==1)
            {
                LL q=V[V.size()-1];
                LL p=q*ai[s];
                V[V.size()-1]=p;
                sum=sum-q+p;
            }
            else
            {
                V.push_back(ai[s]);
                sum=sum+ai[s];
            }
            lr[i][s]=sum;
            limit[i][s]=V[V.size()-1];
        }

    }

}
void init()
{
    len=strlen(ch+1);
    st=0;
    for(int i=1; i<=len; i++)
    {
        if(ch[i]=='*')
            bi[st]=1;
        else if(ch[i]=='+')
            bi[st]=0;
        else
        {
            st++;
            ai[st]=ch[i]-'0';
        }
    }
    get();
}
void play()
{
    LL MAX=0;
    for(int i=1; i<=st; i++)
    {
        vector<LL>V;
        LL sum=0;
        for(int j=i; j<=st; j++)
        {
            if(j==i)
            {
                V.push_back(ai[i]);
                sum=ai[i];
            }
            else
            {
                if(bi[j-1]==1)
                {
                    LL q=V[V.size()-1];
                    LL p=q*ai[j];
                    V[V.size()-1]=p;
                    sum=sum-q+p;
                }
                else
                {
                    V.push_back(ai[j]);
                    sum=sum+ai[j];
                }
            }
            int ln=i-1;
            int rn=j+1;
            LL ll=lr[0][ln];
            LL rr=lr[1][rn];
            if(ln>=1&&rn<=st)
                if(bi[ln]==1&&bi[j]==1)
                    MAX=max(MAX,ll+rr-limit[0][ln]-limit[1][rn]+limit[0][ln]*limit[1][rn]*sum);
                else if(bi[ln]==1)
                    MAX=max(MAX,ll+rr-limit[0][ln]+limit[0][ln]*sum);
                else if(bi[j]==1)
                    MAX=max(MAX,ll+rr-limit[1][rn]+limit[1][rn]*sum);
                else
                    MAX=max(MAX,ll+rr+sum);
            else if(ln>=1)
                if(bi[ln]==1)
                    MAX=max(MAX,ll-limit[0][ln]+limit[0][ln]*sum);
                else
                    MAX=max(MAX,ll+sum);
            else if(rn<=st)
                if(bi[j]==1)
                    MAX=max(MAX,rr-limit[1][rn]+limit[1][rn]*sum);
                else
                    MAX=max(MAX,rr+sum);
            else
                MAX=max(MAX,sum);
        }
    }
    printf("%I64d\n",MAX);
}
int main()
{
    while(scanf("%s",ch+1)!=EOF)
    {
        init();
        play();

    }
//    cout << "Hello world!" << endl;
    return 0;
}