diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 150 |
1 files changed, 94 insertions, 56 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 3083cdc..dd6d90b 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,77 +1,115 @@ #include <iostream> #include <vector> +#include <climits> +#include <cassert> //#include <gtest/gtest.h> using std::vector; +using std::string; +using std::max; +using std::min; -vector<vector<int>> optimalWeight2DArray(int W, vector<int> &w2) { - int j = w2.size(); -// int value[W + 1][j + 1]; - vector<vector<int> > value(W + 1, vector<int>(j + 1)); +long eval(long a, long b, char op) { + if (op == '*') { + return a * b; + } else if (op == '+') { + return a + b; + } else if (op == '-') { + return a - b; + } else { + assert(0); + } +} - for (int i = 0; i < j + 1; i++) { - for (int w = 0; w < W + 1; w++) { - if (i == 0 || w == 0) { - value[w][i] = 0; - continue; - } - value[w][i] = value[w][i - 1]; - if (w2[i - 1] <= w) { - int val = value[w - w2[i - 1]][i - 1] + w2[i - 1]; - if (value[w][i] < val) { - value[w][i] = val; - } - } - } +vector<long> minAndMax(vector<vector<long>> &m, vector<vector<long>> &M, + vector<char> &op, int i, int j) { + long minValue = LONG_MAX; + long maxValue = LONG_MIN; + vector<long> result; + for (int k = i; k < j; k++) { + long a = eval(M[i][k], M[k + 1][j], op[k]); + long b = eval(M[i][k], m[k + 1][j], op[k]); + long c = eval(m[i][k], M[k + 1][j], op[k]); + long d = eval(m[i][k], m[k + 1][j], op[k]); + minValue = min(minValue, min(a, min(b, min(c, d)))); + maxValue = max(maxValue, max(a, max(b, max(c, d)))); } - return value; + result.push_back(minValue); + result.push_back(maxValue); + return result; } - -int partition3(vector<int> &a) { - if (a.size() < 3) - return 0; - int sum = 0; - for (int i = 0; i < a.size(); i++) { - sum = sum + a[i]; +long getMaxValue(vector<int> &d, vector<char> &op) { + vector<vector<long>> m(d.size(), vector<long>(d.size())); + vector<vector<long>> M(d.size(), vector<long>(d.size())); + for (int i = 0; i < d.size(); i++) { + m[i][i] = d[i]; + M[i][i] = d[i]; } - if (sum % 3 != 0) - return 0; - int W = sum / 3; - vector<vector<int> > values = optimalWeight2DArray(W, a); - int count = 0; - for (int i = 1; i < a.size() + 1; i++) { - for (int w = 1; w < W + 1; w++) { - if (values[w][i] == W) - count = count + 1; + for (int s = 0; s < op.size(); s++) { + for (int i = 0; i < d.size() - s; i++) { + int j = i + s + 1; + if (j >= d.size()) + break; + vector<long> tempMinAndMax = minAndMax(m, M, op, i, j); + m[i][j] = tempMinAndMax[0]; + M[i][j] = tempMinAndMax[1]; } } - if (count >= 3) - return 1; - else - return 0; + return M[0][d.size() - 1]; +} + +long getMaxValue(string exp) { + int x = exp.length(); + vector<int> d; + vector<char> op; + + for (int i = 0; i < x - 1; i = i + 2) { + d.push_back(exp[i] - '0'); + op.push_back(exp[i + 1]); + } + d.push_back(exp[x - 1] - '0'); + return getMaxValue(d, op); } -//TEST(KnapsackPartition3, t1) { -// vector<int> a = { 3, 3, 3, 3 }; -// ASSERT_EQ(0, partition3(a)); + +//vector<int> parseExp(string exp) { +// int x = exp.length(); +// vector<int> d; +// vector<char> op; +// +// for (int i = 0; i < x - 1; i = i + 2) { +// d.push_back(exp[i] - '0'); +// op.push_back(exp[i + 1]); +// } +// d.push_back(exp[x - 1] - '0'); +// return d; +//// return getMaxValue(d, op); //} // -//TEST(KnapsackPartition3, t2) { -// vector<int> a = { 30 }; -// ASSERT_EQ(0, partition3(a)); +//TEST(MaxExpValue, t1) { +// string exp = "1+5"; +// ASSERT_EQ(6, getMaxValue(exp)); //} // -//TEST(KnapsackPartition3, t3) { -// vector<int> a = { 1, 2, 3, 4, 5, 5, 7, 7, 8, 10, 12, 19, 25 }; -// ASSERT_EQ(1, partition3(a)); +//TEST(MaxExpValue, t2) { +// string exp = "5-8+7*4-8+9"; +// ASSERT_EQ(200, getMaxValue(exp)); +//} +//TEST(MaxExpValue, t3) { +// string exp = "1+2-3*4-5"; +// ASSERT_EQ(6, getMaxValue(exp)); +//} +//TEST(MaxExpValue, t4) { +// string exp = "1+2*3"; +// ASSERT_EQ(9, getMaxValue(exp)); +//} +// +//TEST(ParseExpTest, t1) { +// string exp = "1+5"; +// ASSERT_EQ(1, parseExp(exp)[0]); //} - int main() { - int n; - std::cin >> n; - vector<int> A(n); - for (size_t i = 0; i < A.size(); ++i) { - std::cin >> A[i]; - } - std::cout << partition3(A) << '\n'; + string s; + std::cin >> s; + std::cout << getMaxValue(s) << '\n'; } |