You can solve this problem by solely making cuts of size S. |
I'm not sure that I can convince you that this assumption is true, but it's the assumption I made, and it was very good at limiting the scope of my recursion. The recursion works as follows:
/* Topcoder TCO 2017, Q1A 500-Pointer - CheeseSlicing James S. Plank Fri Apr 7 16:05:47 EDT 2017 */ #include <string> #include <vector> #include <list> #include <cmath> #include <algorithm> #include <map> #include <set> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; class CheeseSlicing { public: int totalArea(int A, int B, int C, int S); vector < vector < vector <int> > >Cache; }; int CheeseSlicing::totalArea(int A, int B, int C, int S) { int i, j, best; vector <int> Sorted; /* Initialize the cache if this is the very first call. */ if (Cache.size() == 0) { Cache.resize(A+1); for (i = 0; i < Cache.size(); i++) { Cache[i].resize(B+1); for (j = 0; j < Cache[i].size(); j++) Cache[i][j].resize(C+1, -1); } } /* Memoization. */ if (Cache[A][B][C] != -1) return Cache[A][B][C]; /* Sort the slices -- this makes it easier to find the "shortest" slice. */ Sorted.push_back(A); Sorted.push_back(B); Sorted.push_back(C); sort(Sorted.begin(), Sorted.end()); /* Base case: If the smallest side is less than S, then you have a bad slice -- return 0. It's up to you whether you want to put this answer into the cache. It's actually more efficient if you do, but it's still constant time if you dont, so I don't. */ if (Sorted[0] < S) return 0; /* Otherwise, first calculate the surface area if you make no cuts. */ best = Sorted[1] * Sorted[2]; /* Then, for each side, if slicing along that side yields two "good" pieces, go ahead and make the recursive call for each of these, and sum up the results. Use the maximum of these. */ if (A-S >= S) { i = totalArea(A-S, B, C, S) + totalArea(S, B, C, S); if (i > best) best = i; } if (B-S >= S) { i = totalArea(A, B-S, C, S) + totalArea(A, S, C, S); if (i > best) best = i; } if (C-S >= S) { i = totalArea(A, B, C-S, S) + totalArea(A, B, S, S); if (i > best) best = i; } Cache[A][B][C] = best; return best; } |