Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define readFile freopen("input","r",stdin)
- #define writeFile freopen("output","w",stdout)
- #define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- typedef unsigned long long ull;
- typedef long long LL;
- typedef pair<long long,long long> ii;
- const double eps = 1e-10;
- const long long mod = 1e9+7;
- const int INF = 1e9;
- const int N = 101;
- int n;
- ull dp[N][N],vis[N][N],cntr;
- string s;
- ull rec(int x,int y){
- if (x==y) return s[x]-'0';
- if (vis[x][y]==cntr) return dp[x][y];
- vis[x][y] = cntr;
- ull num = s[y]-'0';
- ull ret = 0;
- if (s[y-1]=='*'){
- ret = rec(x,y-2)*num;
- for(int i=x+1;i<y-1;i+=2){
- if (s[i]=='+') ret = max(ret,rec(x,i-1)+(rec(i+1,y-2)*num));
- else ret = max(ret,(rec(x,i-1)*rec(i+1,y-2))*num);
- }
- }
- else{
- ret = rec(x,y-2)+num;
- for(int i=x+1;i<y-1;i+=2){
- if (s[i]=='+') ret = max(ret,(rec(x,i-1)+rec(i+1,y-2))+num);
- else ret = max(ret,rec(x,i-1)*(rec(i+1,y-2)+num));
- }
- }
- return dp[x][y] = ret;
- }
- ull recm(int x,int y){
- if (x==y) return s[x]-'0';
- if (vis[x][y]==cntr) return dp[x][y];
- vis[x][y] = cntr;
- ull num = s[y]-'0';
- ull ret = 0;
- if (s[y-1]=='*'){
- ret = recm(x,y-2)*num;
- for(int i=x+1;i<y-1;i+=2){
- if (s[i]=='+') ret = min(ret,recm(x,i-1)+(recm(i+1,y-2)*num));
- else ret = min(ret,(recm(x,i-1)*recm(i+1,y-2))*num);
- }
- }
- else{
- ret = recm(x,y-2)+num;
- for(int i=x+1;i<y-1;i+=2){
- if (s[i]=='+') ret = min(ret,recm(x,i-1)+(recm(i+1,y-2)+num));
- else ret = min(ret,recm(x,i-1)*(recm(i+1,y-2)+num));
- }
- }
- return dp[x][y] = ret;
- }
- int main() {
- #ifndef ONLINE_JUDGE
- readFile;
- // writeFile;
- #endif
- fastIO;
- cin>>n;
- while(n--){
- cin>>s;
- cntr++;
- cout<<rec(0,s.size()-1)<<" ";
- cntr++;
- cout<<recm(0,s.size()-1)<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement