CodeForces-552E. Vanya and Brackets

本是古典何须时尚 2022-08-01 13:54 164阅读 0赞

/*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;
    }