ThreeMines
SRM 315 · 2006-08-09 · by Cosmin.ro
SRM 315 · 2006-08-09 · by Cosmin.ro · Dynamic Programming
Problem Statement
Problem Statement
A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a non-empty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from three different non-overlapping mines. You are to choose these mines to maximize the total profit.
You are given a String[] field where each character represents the profit value of a single cell. Characters 'a' to 'z' correspond to the numbers 0 through 25 and characters 'B' to 'Z' correspond to numbers -1 through -25. The jth char in the ith element of field is the profit value of the cell at row i, column j.
You are given a String[] field where each character represents the profit value of a single cell. Characters 'a' to 'z' correspond to the numbers 0 through 25 and characters 'B' to 'Z' correspond to numbers -1 through -25. The jth char in the ith element of field is the profit value of the cell at row i, column j.
Constraints
- field will contain between 1 and 30 elements, inclusive.
- Each element of field will contain between 1 and 30 characters, inclusive.
- Each character of field will be from the set 'a'..'z' and 'B'..'Z'.
- All elements of field will contain the same number of characters.
- field must contain at least 3 cells.
Examples
0)
{
"bbbb",
"bBBB",
"BBbb",
"BBBB"}
Returns: 7
One of the optimal solutions is the following: One mine contains all cells in the first row, the second mine contains the cell (1, 0), and the third mine contains the cells (2, 2) and (2, 3).
1)
{"cfCBDCbcdZb"}
Returns: 14
A single row example.
2)
{"d", "c", "B", "m", "Z", "h", "g", "B", "z", "G", "H", "b", "Y"}
Returns: 54
A single column example.
3)
{
"hBhh",
"BBBB",
"BBBB",
"hBhh",
"hBhh"}
Returns: 62
This test has only one solution.
4)
{
"BB",
"BB"}
Returns: -3
It is possible for the maximum possible profit to be negative.
18)
{"aaaaaa", "aBddBa", "adzzda", "adzHaa", "abdaaa", "aaaaaa"}
Returns: 94
greedy testcase
32)
{"hBZaBz","dhbhhB","dhbBaa","cBZaaa"}
Returns: 69
hBZaBz dhbhhB dhbBaa cBZaaa
Submissions are judged against all 75 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ThreeMines with a public method int maximumProfit(vector<string> field) · 75 test cases · 2 s / 256 MB per case