Advertisement
Guest User

Untitled

a guest
Jul 19th, 2016
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define readFile freopen("input","r",stdin)
  4. #define writeFile freopen("output","w",stdout)
  5. #define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  6. typedef unsigned long long ull;
  7. typedef long long LL;
  8. typedef pair<long long,long long> ii;
  9. const double eps = 1e-10;
  10. const long long mod = 1e9+7;
  11. const int INF = 1e9;
  12. const int N = 101;
  13.  
  14. int n;
  15. ull dp[N][N],vis[N][N],cntr;
  16. string s;
  17.  
  18. ull rec(int x,int y){
  19.     if (x==y) return s[x]-'0';
  20.     if (vis[x][y]==cntr) return dp[x][y];
  21.     vis[x][y] = cntr;
  22.     ull num = s[y]-'0';
  23.     ull ret = 0;
  24.     if (s[y-1]=='*'){
  25.         ret = rec(x,y-2)*num;
  26.         for(int i=x+1;i<y-1;i+=2){
  27.             if (s[i]=='+') ret = max(ret,rec(x,i-1)+(rec(i+1,y-2)*num));
  28.             else ret = max(ret,(rec(x,i-1)*rec(i+1,y-2))*num);
  29.         }
  30.     }
  31.     else{
  32.         ret = rec(x,y-2)+num;
  33.         for(int i=x+1;i<y-1;i+=2){
  34.             if (s[i]=='+') ret = max(ret,(rec(x,i-1)+rec(i+1,y-2))+num);
  35.             else ret = max(ret,rec(x,i-1)*(rec(i+1,y-2)+num));
  36.         }
  37.     }
  38.     return dp[x][y] = ret;
  39. }
  40. ull recm(int x,int y){
  41.     if (x==y) return s[x]-'0';
  42.     if (vis[x][y]==cntr) return dp[x][y];
  43.     vis[x][y] = cntr;
  44.     ull num = s[y]-'0';
  45.     ull ret = 0;
  46.     if (s[y-1]=='*'){
  47.         ret = recm(x,y-2)*num;
  48.         for(int i=x+1;i<y-1;i+=2){
  49.             if (s[i]=='+') ret = min(ret,recm(x,i-1)+(recm(i+1,y-2)*num));
  50.             else ret = min(ret,(recm(x,i-1)*recm(i+1,y-2))*num);
  51.         }
  52.     }
  53.     else{
  54.         ret = recm(x,y-2)+num;
  55.         for(int i=x+1;i<y-1;i+=2){
  56.             if (s[i]=='+') ret = min(ret,recm(x,i-1)+(recm(i+1,y-2)+num));
  57.             else ret = min(ret,recm(x,i-1)*(recm(i+1,y-2)+num));
  58.         }
  59.     }
  60.     return dp[x][y] = ret;
  61. }
  62.  
  63. int main() {
  64.     #ifndef ONLINE_JUDGE
  65.    readFile;
  66. //    writeFile;
  67. #endif
  68.    fastIO;
  69.    cin>>n;
  70.    while(n--){
  71.        cin>>s;
  72.        cntr++;
  73.        cout<<rec(0,s.size()-1)<<" ";
  74.        cntr++;
  75.        cout<<recm(0,s.size()-1)<<"\n";
  76.    }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement