1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <iostream> #include <memory.h> #include <cmath> #include <stack> using namespace std; long dp[10][10][2]; bool visit[10][10]; string str; int setPostfix(string str) { stack<int> s; stack<char> op; for(int i = 0; i < str.length(); i++) { if ('0' <= str[i] && str[i] <= '9') { s.push(str[i] & 0b1111); } else { if(op.empty()) { op.push(str[i]); } else { if(op.top() == '*' && str[i] != '*') { int a, b; a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(a * b); op.pop(); } if(!op.empty() && op.top() == '-') { int a = s.top(); a *= -1; s.pop(); s.push(a); op.pop(); op.push('+'); } op.push(str[i]); } } } while(!op.empty()) { int a, b; a = s.top(); s.pop(); b = s.top(); s.pop(); switch (op.top()) { case '+' : s.push(b + a); break; case '-' : s.push(b - a); break; case '*' : s.push(b * a); break; } op.pop(); } return s.top(); } pair<long,long> calc(int f, int e) { if(visit[f][e]) return make_pair(dp[f][e][0],dp[f][e][1]); visit[f][e] = true; dp[f][e][0] = dp[f][e][1] = setPostfix(str.substr(2*f, (e-f)*2+1)); for(int i = f; i < e; i++){ switch (str[i*2+1]) { case '+' : dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) + max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) + min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) + max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) + min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) + max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) + min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) + max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) + min(calc(i+1,e).first,calc(i+1,e).second)); break; case '-' : dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) - max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) - min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) - max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) - min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) - max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) - min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) - max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) - min(calc(i+1,e).first,calc(i+1,e).second)); break; case '*' : dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) * max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], max(calc(f,i).first, calc(f,i).second) * min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) * max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][0] = max(dp[f][e][0], min(calc(f,i).first, calc(f,i).second) * min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) * max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], max(calc(f,i).first, calc(f,i).second) * min(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) * max(calc(i+1,e).first,calc(i+1,e).second)); dp[f][e][1] = min(dp[f][e][1], min(calc(f,i).first, calc(f,i).second) * min(calc(i+1,e).first,calc(i+1,e).second)); break; } } return make_pair(dp[f][e][0],dp[f][e][1]); } int main() { int n; cin>>n>>str; cout<<max(calc(0,(str.length()-1)/2).first, calc(0,(str.length()-1)/2).second); }
|