summaryrefslogtreecommitdiff
path: root/PlaygroundCpp/Sources
diff options
context:
space:
mode:
Diffstat (limited to 'PlaygroundCpp/Sources')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp150
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';
}