SPOJ LISA (MATRIX CHAIN MULTIPLICATION VARIATION)

https://www.spoj.com/problems/LISA/

#include<bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define MOD 1000000007
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define FOR(a,n) for(int i=a;i<n;++i)
#define arrin(n) for(int i=0; i < n; ++i) cin>>arr[i];
#define arrout(n) for(int i=0; i < n; ++i) cout<<arr[i]<<" ";cout<<nl;
#define nl "\n"
#define mp make_pair
typedef unsigned long long ull;
typedef long long int ll;
typedef long double ld;
using namespace std;
const double pi=acos(-1.0);
const double pii=2*pi;
const double eps=1e-6;
const double inf=1e15;
typedef pair<ll,ll> iPair;
typedef priority_queue< iPair, vector <iPair> , greater<iPair>> Pq;
ll dp[2005][2005];
int main()
{
  fastio();
  // #ifndef ONLINE_JUDGE
  //     freopen("input.txt","r",stdin);
  //     freopen("output.txt","w",stdout);
  // #endif
  ll t;
  cin>>t;
  while(t--)
  {
     string s;
     cin>>s;
     ll n=s.length();
     vector<ll> num,sign; //sign +:0 *:1
     for(ll i=0;i<n;i++)
     {
        if(i%2==0) num.pb(s[i]-48);
        else 
        {
          if(s[i]=='+') sign.pb(0);
          else sign.pb(1);
        }
     }
     n=num.size();
     ll dp[n][n];
     memset(dp,0,sizeof(dp));
     for(ll i=0;i<n;i++) dp[i][i]=num[i];
     for(ll z=1;z<n;z++)
     {
        for(ll i=0;i+z<n;i++)
        {
           ll j=i+z;
           ll mx=0;
           for(ll k=i;k<j;k++)
           {
              if(sign[k]==0) mx=max(mx,dp[i][k]+dp[k+1][j]);
              else mx=max(mx,dp[i][k]*dp[k+1][j]);
           }
           dp[i][j]=mx; 
        }
     }
     // for(ll i=0;i<n;i++)
     // {
     //    for(ll j=0;j<n;j++) cout<<dp[i][j]<<" ";
     //    cout<<nl;
     // }
     ll ansmax=dp[0][n-1];
     memset(dp,0,sizeof(dp));
     for(ll i=0;i<n;i++) dp[i][i]=num[i];
     for(ll z=1;z<n;z++)
     {
        for(ll i=0;i+z<n;i++)
        {
           ll j=i+z;
           ll mx=MOD;
           for(ll k=i;k<j;k++)
           {
              if(sign[k]==0) mx=min(mx,dp[i][k]+dp[k+1][j]);
              else mx=min(mx,dp[i][k]*dp[k+1][j]);
           }
           dp[i][j]=mx; 
        }
     }
     // for(ll i=0;i<n;i++)
     // {
     //    for(ll j=0;j<n;j++) cout<<dp[i][j]<<" ";
     //    cout<<nl;
     // }
     ll ansmin=dp[0][n-1];
     cout<<ansmax<<" "<<ansmin<<nl;
  }
  //std::cout <<fixed<< std::setprecision(15) << ans << '\n';
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}