CodeForces-552E. Vanya and Brackets-蒲公英云

CodeForces-552E. Vanya and Brackets

/*CF e题 给定一个表达式，只添加一对括号，使得这个表达式的值最大
* 由于乘号比较少，枚举括号的位置就行；
* 左括号的位置一定在乘号的右边，右括号的位置一定在乘号的左边，
* 这样才能使得表达式的值最大，否则移动括号一定能找到比较大的值
*/
#include<map>
#include<vector>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#define inf 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int in()
{
    int res=0;char c;
    while((c=getchar())<'0' || c>'9');
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res;
}
stack<ll> num;
stack<ll> num2;
stack<char> ch;
ll calc(string & s)
{
    while(num.size())num.pop();
    while(num2.size())num2.pop();
    while(ch.size())ch.pop();
    int n=s.size();
    bool have=0;
    int k1,k2;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='(')
           {
               have=1;
               k1=i;
               ++i;
               while(s[i]!=')')
               {
                   if(s[i]=='*')
                   {
                       ch.push(s[i]);
                   }
                   else if(s[i]>='0' && s[i]<='9')
                   {
                       if(ch.size() && ch.top()=='*')
                       {
                           ll t1 = s[i]-'0';
                           ll t2 = num.top();
                           num.pop();
                           ch.pop();
                           num.push(t1*t2);
                       }
                       else num.push(s[i]-'0');
                   }
                   ++i;
               }
               k2=i;
               break;
           }
    }
    ll tmp=0;
    while(num.size())
    {
        tmp+=num.top();
        num.pop();
    }
    string t=".";
    if(have)s.replace(k1,k2-k1+1,t);
    //cout<<s<<endl;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]=='*')ch.push(s[i]);
        else if((s[i]>='0' && s[i]<='9') || s[i]=='.')
           {
               if(ch.size() && ch.top()=='*')
               {
                   ll t1;
                   if(s[i]!='.')t1 = s[i]-'0';
                   else t1 = tmp;
                   ll t2 = num.top();
                   num.pop();
                   ch.pop();
                   num.push(t1*t2);
               }
               else num.push(s[i]=='.'? tmp:s[i]-'0');
           }
    }
    ll res=0;
    while(num.size())
    {
        res+=num.top();
        //cout<<num.top()<<endl;
        num.pop();
    }
    //cout<<"res=="<<res<<endl;
    return res;
}
vector<int> vec;
int main()
{
    string s,t;
    cin>>s;
    t=s;
    vec.clear();
    int n=s.size();
    vec.push_back(-1);
    for(int i=1;i<n;i+=2)
    {
        if(s[i]=='*')
        {
            vec.push_back(i);
        }
    }
    vec.push_back(n);
    n=vec.size();
    ll ans=calc(s);
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            s=t;
            s.insert(vec[i]+1,1,'(');
            s.insert(vec[j]+1,1,')');
            //cout<<s<<endl;
            ans=max(ans,calc(s));
        }
    }
    cout<<ans<<endl;
    return 0;
}