Removing Boxes in Groups
Boxes of various colours sit in a row. One move removes a CONTIGUOUS group of boxes that all share a colour, scoring the SQUARE of how many were removed. The remaining boxes close up, so boxes that were separated can become adjacent.
Print the largest total score.
1 3 2 2 2 3 4 3 1 -> 23
1 1 1 -> 9 remove all three at once
1 2 3 -> 3 three separate removals of one box each
## Why squaring changes everything
If the score were the COUNT, every order would give the same total and there would be nothing to decide.
Squaring makes removing boxes together strictly better than removing them apart:
(a + b)^2 > a^2 + b^2. So the whole problem is about clearing boxes OUT OF THE WAY to let
same-coloured boxes meet.
1 2 1 answers 5, not 3: remove the 2 first, then the two 1s together for 4.
## Why a two-index state fails
The natural state is dp[i][j] for the range i..j. It is not enough.
When the range i..j is processed, boxes of the same colour as box[i] may already be
waiting to its LEFT, outside the range, because everything between them was removed. How
many are waiting changes what i is worth, and the range alone does not record it.
## The third index
go(i, j, k) = the best score for boxes i..j, given that k boxes of colour box[i]
are already attached immediately to the left of i
Two moves from that state:
remove them now (k+1)^2 + go(i+1, j, 0)
save them for each m > i with box[m] == box[i]:
go(i+1, m-1, 0) + go(m, j, k+1)
The second line is the interesting one: clear the stretch between i and m completely,
which lets the boxes at i join the group at m, and carry the count forward.
Adding a counter to the state to remember something that happened OUTSIDE the range is the move here. It is what turns an impossible two-dimensional formulation into a workable three-dimensional one, and the same idea is why problem 499 caps a profit axis.
## Merging the leading run
Before branching, absorb any boxes immediately after i that share its colour into k.
That is not required for correctness but it removes a large number of equivalent states.
## Removing whole runs is enough
The statement allows removing any contiguous same-coloured group, including part of a run. It never helps: because the score is convex, removing a whole run scores at least as much as removing it in pieces, and leaving part of a run behind is dominated by leaving all of it.
That was checked directly, comparing a search over all partial removals against one over maximal runs only, on 400 random inputs with no difference.
## Boundaries
1 answers 1. 1 2 3 answers 3, with nothing to gain by any order.
1 2 1 2 1 answers 11: remove the two 2s separately for 1 each, then the three 1s for 9.
2 2 2 2 answers 16, one move.
## Cost
Time O(n^4) in the worst case. Space O(n^3).