Problem Info
Type: Regional
Continent: South America
Year: 2008
Link: 4212 - Candy
Problem Statement
In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of $M x N$ boxes). Each box has a number indicating how many candies it contains.
The contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. The contestant continues to pick a box until there are no candies left.
Can you maximize the number of candies he can pick?
Explanation
There's a presentation I've written to teach how to solve the problem. It is in Spanish, I don't have enough time now to write the explanation here but I will as soon as I can.
The presentation: 4212-Candy.pdf
Code
The C++ code that solves the problem using Top-Down approach with memoization is the following(4212-memo.cpp):
#include <iostream> #include <algorithm> #include <stdint.h> #include <map> using namespace std; uint32_t row[100002]; uint32_t max_rows[100002]; uint64_t f(uint32_t* array, uint32_t index, uint32_t size, map<uint32_t, uint64_t>& memo) { if (index == size - 1) return array[index]; if (index == size - 2) return max(array[index], array[index + 1]); if (memo.find(index) != memo.end()) return memo[index]; uint64_t tmp = array[index] + f(array, index + 2, size, memo); tmp = max(tmp, f(array, index + 1, size, memo)); memo[index] = tmp; return tmp; } int main() { uint32_t n, m; cin >> m >> n; map<uint32_t, uint64_t> memo; while (m > 0) { for (uint32_t i(0); i < m; ++i) { for (uint32_t j(0); j < n; ++j) { cin >> row[j]; } memo.clear(); max_rows[i] = f(row, 0, n, memo); } memo.clear(); cout << f(max_rows, 0, m, memo) << '\n'; cin >> m >> n; } }
The C++ code for the Bottom-Up approach is the following(4212.cpp):
#include <iostream> #include <algorithm> #include <stdint.h> using namespace std; uint32_t row[100002]; uint32_t max_rows[100002]; uint32_t dp(uint32_t* r, uint32_t size) { if (size > 1) { r[1] = max(r[0], r[1]); } for (uint32_t i(2); i < size; ++i) { r[i] = max(r[i-1], r[i] + r[i-2]); } return r[size-1]; } int main() { uint32_t n, m; cin >> m >> n; while (m > 0) { for (uint32_t i(0); i < m; ++i) { for (uint32_t j(0); j < n; ++j) { cin >> row[j]; } max_rows[i] = dp(row, n); } cout << dp(max_rows, m) << '\n'; cin >> m >> n; } }
