Construct biggest stacked tower with restriction

Problem

The problem is to build the tallest tower made up of cylinders, respecting all the rules.

• Will be arranged on the table, an amount of \$N\$ cylinders.

• Each cylinder has one color: Red, orange, green or blue.

• Each cylinder has one heigth \$h\$ and a base with radius of size \$r\$.

• To the build the tower, the cylinders should to be stacked, and the

top cylinder should ever have the base smaller that the base of the
cylinder below it. Except the first cylinder, it can have the base of
any size, since there is no other cylinder below it.

There are also some restrictions very interesting on colors of the cylinders. They are described below.

• A red cylinder cannot to be put on an orange cylinder

• An orange cylinder cannot to be put on a blue cylinder

• A blue cylinder cannot to be put on a green cylinder

• A green cylinder cannot to be put on a red cylinder

Input


The input contains several test cases. The first line of each test case contains an integer \$N\$ \$(1 \le N \le 10^3)\$, representing the number of cylinders arranged on the table, following N rows, each row having a height \$h\$ \$(1 \le h \le 1000)\$ of the cylinder in centimeters, the radius \$r\$ \$(1 \le r \le 1000)\$ of the cylinder base and a word \$p\$, representing the color of the cylinder. The word can be: RED, ORANGE, GREEN, or BLUE. The end of input is indicated as \$N = 0\$, which should not be processed.

Output


For each test case, your program should print a single line with the value the height of the largest cylinders tower that can be built, followed by the word "centimeter(s)”.

Sample Input

5   
5 3 RED    
4 2 ORANGE   
1 1 GREEN    
3 5 ORANGE    
2 4 BLUE    
3    
10 10 ORANGE    
5 10 GREEN    
6 5 RED    
0

Sample Output

15 centimeter(s)    
11 centimeter(s)

I've tried to solve this problem with dynamic programming.

```
#include
#include
#include
#include
#include

#define MAX 1000

#define NON -1
#define RED 1
#d

-
An immediate candidate for optimisation is canPut. The color restrictions reveal some symmetry. If you map colors to numbers 0..3, you may notice that the each restrictions actually mean the same thing:

(cylinder[i].c - cylinder[last_cylinder_onStack].c) % 4 == 1

is prohibited. This is the only condition to be tested.

-
I would also sort the cylinders by radius. This way you don't need to manually track the cylinders, and the dp loop reduces to

for (int c = i + 1; c < size; ++c) {
    if(canPut(c, last_cylinder_onStack)) {
        maxHeight = std::max(maxHeight, cylinder[c].h + dp(i + 1, size, c));
    }
}

-
A map is a very heavyweight object. It has much memory overhead, doesn't have a good referential locality, and has a logarithmic time complexity. A map of maps is even more heavy. Since all your keys are integers, a simple 2D array, or vector of vectors if you wish (with constant insert and access time) would serve you much better.

StackExchange Code Review Q#104662, answer score: 3