bhupixb

Maximize expression

Jan 26th, 2020
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. //https://www.spoj.com/problems/LISA/
  2.  
  3. // I can't tell you what it really is,
  4. // I can only tell you what it feels like.
  5. #include "bits/stdc++.h"
  6. using namespace std;
  7. #define int long long
  8.  
  9. auto operator+=(pair<int,int> &x, const pair<int,int> &y) {
  10. x.first += y.first;
  11. x.second += y.second;
  12. return x;
  13. }
  14. auto operator*=(pair<int,int> &x, const pair<int,int> &y) {
  15. x.first *= y.first;
  16. x.second *= y.second;
  17. return x;
  18. }
  19. auto operator-=(pair<int,int> &x, const pair<int,int> &y) {
  20. x.first -= y.first;
  21. x.second -= y.second;
  22. return x;
  23. }
  24.  
  25. const int N = 102;
  26. const int inf = numeric_limits<int>::max();
  27. const int ninf = numeric_limits<int>::min();
  28. char s[N];
  29. int a[N];
  30. pair<int,int> dp[N][N];
  31. const pair<int,int> ok = make_pair(-1,-1);
  32.  
  33. void pre() {
  34. for (int i = 0; i < N; ++i) {
  35. for (int j = 0; j < N; ++j) {
  36. dp[i][j] = ok;
  37. }
  38. }
  39. }
  40.  
  41. pair<int,int> go(int l, int r) {
  42. if (l == r) return make_pair(a[l],a[l]);
  43. if (dp[l][r] != ok) return dp[l][r];
  44. int ans = inf;
  45. pair<int,int> findL, findR;
  46. int mn = inf, mx = ninf;
  47. for (int i = l; i < r; ++i) {
  48. findL = go(l,i);
  49. findR = go(i+1,r);
  50. switch(s[i]) {
  51. case '+':
  52. findL += findR; break;
  53. case '*':
  54. findL *= findR; break;
  55. case '-':
  56. findL -= findR; break;
  57. }
  58. mn = min(mn, findL.first);
  59. mx = max(mx ,findL.second);
  60. }
  61. return dp[l][r] = make_pair(mn, mx);
  62. }
  63. signed main() {
  64. ios::sync_with_stdio(false);
  65. cin.tie(0);
  66. cout.tie(0);
  67. string str;
  68. int t = 1; cin >> t;
  69. while (t--) {
  70. int n = 0;
  71. pre();
  72. cin >> str;
  73. for (int i = 0; i < str.size(); ++i) {
  74. if (isdigit(str[i])) a[n++] = str[i] - '0';
  75. else s[n-1] = str[i];
  76. }
  77. auto it = go(0,n-1);
  78. cout << it.second << ' ' << it.first << '\n';
  79. }
  80. return 0;
  81. }
  82. // 1). Try forming/rearranging the equations if any
  83. // 2). If problem asks to count, try counting in reverse(it can be easier sometimes)
Add Comment
Please, Sign In to add comment