移除盒子（进阶版：带颜色限制的移除成本）
题目描述
你面前有一排盒子，每个盒子有一个颜色（用正整数表示），这些盒子排成一列。
你可以进行以下操作：
- 选择一个盒子，然后移除它。但移除操作有特殊的计分规则：
如果你移除了某个颜色为 \(c\) 的盒子，你获得的分数是：
\[ \text{score} = (\text{本次移除的连续同色盒子数量})^2 - \text{cost}(c) \]
其中 \(\text{cost}(c)\) 是一个给定的函数，表示移除颜色 \(c\) 的单个盒子的“固定成本”（正值表示成本，会减少分数，负值表示奖励，会增加分数）。
注意：
- 你一次可以移除一个或多个连续相同颜色的盒子（即必须一次性把一段连续相同颜色的盒子全部移除）。
- 移除后，两边的盒子会靠拢，成为相邻。
- 你可以任意选择移除的顺序，目标是最大化总得分。
给定一个整数数组 boxes 表示盒子的颜色序列，以及一个函数 \(\text{cost}(c)\) 返回整数（可能是正、负或零），求最大得分。
示例
盒子序列：[1, 3, 2, 2, 2, 3, 4, 3, 1]
cost(1) = 1, cost(2) = 1, cost(3) = 2, cost(4) = 5
一个可能的操作顺序：
- 先移除
[2,2,2]，得分 = 3² - 1×3 = 9 - 3 = 6 - 剩下
[1,3,3,4,3,1] - 移除
[3,3]，得分 = 2² - 2×2 = 4 - 4 = 0 - 剩下
[1,4,3,1] - 移除
[4]，得分 = 1² - 5×1 = 1 - 5 = -4 - 剩下
[1,3,1] - 移除
[3]，得分 = 1² - 2×1 = 1 - 2 = -1 - 剩下
[1,1] - 移除
[1,1]，得分 = 2² - 1×2 = 4 - 2 = 2
总得分 = 6 + 0 - 4 - 1 + 2 = 3
但这个顺序不一定是最优的，我们需要找到最大得分的策略。
解题思路
这是一个区间动态规划问题，但它比经典的“移除盒子”（Remove Boxes）更复杂，因为每个颜色有不同的移除成本，而且移除一段连续同色盒子时，成本是乘以盒子数量。
我们可以这样定义状态：
设 \(dp[i][j][k]\) 表示在区间 \([i, j]\) 上，在区间左侧（即 \(i\) 位置盒子的左边，但仍在整个序列范围内）有 \(k\) 个颜色与 \(boxes[i]\) 相同的盒子（这 \(k\) 个盒子是之前因为中间某些盒子被移除而暴露出来的，可以与 \(i\) 位置的盒子一起移除，以获得更高分数）。
举例：
对于 [A, ..., A, ...]，如果 \(i\) 位置是 A，而 \(i\) 左边的若干 A 因为中间盒子被移除而可以合并进来，我们用 \(k\) 记录左边可合并的同色盒子数量。
状态转移推导
我们考虑对区间 \([i, j]\) 的第一个盒子（即 \(boxes[i]\)）如何处理：
情况1：将 \(i\) 位置与它左边的 \(k\) 个同色盒子一起移除
我们找到区间内所有颜色等于 \(boxes[i]\) 的盒子，并决定是一次性把所有能合并的（包括左边的 \(k\) 个）一起移除，还是先处理中间部分，让更多同色盒子聚集后再一起移除。
设 \(m\) 是满足 \(i \le m \le j\) 且 \(boxes[m] = boxes[i]\) 的位置集合。
我们可以选择在某个 \(p\) 位置（\(p\) 是 \(m\) 集合中的某个位置，比如第一个匹配的位置）将区间分割，让左边部分与 \(k\) 合并，右边部分单独处理。
但更通用的转移是：
- 将 \(i\) 与后面某个同色位置 \(m\) 及它们之间的所有盒子一起考虑移除，但这样会涉及中间盒子的处理，比较复杂。
经典“移除盒子”问题的转移是：
\[dp[i][j][k] = \max \begin{cases} (k+1)^2 - \text{cost}(c) \times (k+1) + dp[i+1][j][0], & \text{如果 } i=j \\ \max_{m: i < m \le j, \, boxes[m]=boxes[i]} \left[ dp[i+1][m-1][0] + dp[m][j][k+1] \right], & \text{否则} \end{cases} \]
但这个公式是假设一次移除只能移除连续的一段同色盒子，并且在移除盒子 \(i\) 时，我们可以选择将它与后面的同色盒子 \(m\) 及中间的盒子先处理掉，然后 \(m\) 盒子就可以与前面的 \(k+1\) 个盒子（包括 \(i\) 位置）一起移除。
但本题中一次移除必须是连续同色的盒子，所以“与后面同色盒子一起移除”意味着必须把中间不同色的盒子先清空，然后两段同色的盒子才能变成相邻，从而一起移除。
这正是经典“移除盒子”的状态转移逻辑。
因此我们直接采用“移除盒子”的标准 DP 思路，但在计算得分时，修改得分公式。
状态：
\(dp[i][j][k]\) 表示在子数组 \(boxes[i..j]\) 上，在子数组前面（即 \(i\) 的左边，不在 \([i,j]\) 区间内）有 \(k\) 个颜色等于 \(boxes[i]\) 的盒子（这些盒子是之前保留下来，准备与 \(boxes[i]\) 一起移除的）。
目标：\(dp[0][n-1][0]\)
转移方程：
- 如果 \(i > j\)，\(dp = 0\)。
- 如果 \(i = j\)，则我们可以选择移除这个盒子与它左边的 \(k\) 个盒子（都是同色），得分为：
\[ (k+1)^2 - (k+1) \times \text{cost}(boxes[i]) \]
- 如果 \(i < j\)，我们考虑两种选择：
- 选择1：现在就移除 \(i\) 与它左边的 \(k\) 个盒子（即 \(k+1\) 个同色盒子一起移除），然后处理剩下的区间 \([i+1, j]\)，此时左边没有同色盒子累积，所以：
\[ \text{score}_1 = (k+1)^2 - (k+1) \times \text{cost}(boxes[i]) + dp[i+1][j][0] \]
- 选择2：不立即移除 \(i\)，而是保留 \(i\)，让它与后面某个同色的盒子 \(m\) 一起移除。为了做到这一点，我们必须先移除区间 \([i+1, m-1]\) 内的所有盒子，这样 \(i\) 和 \(m\) 才能相邻，并与左边的 \(k\) 个盒子一起移除。
所以我们枚举 \(m \in (i, j]\) 且 \(boxes[m] = boxes[i]\)，然后：
\[ \text{score}_2 = dp[i+1][m-1][0] + dp[m][j][k+1] \]
这里的 $dp[m][j][k+1]$ 表示在区间 $[m, j]$ 上，左边已经有 $k+1$ 个同色盒子（原来的 $k$ 个加上位置 $i$ 的盒子），这些将在后续一起移除。
取两种选择的最大值：
\[ dp[i][j][k] = \max(\text{score}_1, \max_{m} \text{score}_2) \]
算法步骤
- 输入数组
boxes和 cost 函数。 - 预处理：对每个区间 \([i, j]\) 和 \(k\) 计算 dp 值。
注意 \(k\) 最大可能为 \(n\)，但实际不会超过区间内同色盒子的总数，可以用记忆化搜索优化。 - 采用记忆化搜索实现：
- 如果 \(i > j\)，返回 0。
- 如果已计算过 \(dp[i][j][k]\)，直接返回。
- 否则，先计算选择1的得分。
- 然后遍历 \(m = i+1\) 到 \(j\)，如果 \(boxes[m] = boxes[i]\)，递归计算：
\[ \text{temp} = dfs(i+1, m-1, 0) + dfs(m, j, k+1) \]
更新最大值。
- 记录结果并返回。
- 最终结果 = \(dfs(0, n-1, 0)\)。
复杂度分析
- 状态数：\(O(n^3)\)，因为 \(i, j, k\) 各 \(O(n)\)。
- 每个状态转移需要遍历可能的 \(m\)，最坏 \(O(n)\)，总复杂度 \(O(n^4)\)，在 \(n \le 100\) 时可接受。
优化：可以在预处理时记录每个区间内下一个同色盒子的位置，减少枚举，但最坏情况仍然是 \(O(n^4)\)。 - 空间复杂度：\(O(n^3)\)。
示例演算（简略）
以 boxes = [1, 2, 1]，cost(1)=1, cost(2)=1 为例：
- 计算 dp[0][2][0]：
- 选择1：移除 boxes[0] 和左边0个同色盒子，得分 = 1² - 1×1 = 0，加上 dp[1][2][0] 的结果。
- 选择2：找到 m=2（同色1），则 temp = dp[1][1][0] + dp[2][2][1]。
- dp[1][1][0]：移除 boxes[1] 单独，得 1² - 1×1 = 0。
- dp[2][2][1]：移除 boxes[2] 与左边1个同色盒子（共2个同色盒子），得 2² - 2×1 = 4 - 2 = 2。
所以 temp = 0 + 2 = 2。
- 比较：选择1需要先算 dp[1][2][0]：
dp[1][2][0]：boxes[1] 与 boxes[2] 不同，选择1：移除 boxes[1] 单独，得0，加 dp[2][2][0] = 0，总0；
选择2：无同色 m，所以 dp[1][2][0] = 0。
所以选择1总分 = 0 + 0 = 0。 - 因此 dp[0][2][0] = max(0, 2) = 2。
最终结果 2，对应操作顺序：先移除中间的 2（得分0），剩下 [1,1] 一起移除（得分 2² - 1×2 = 2），总得分 2。
小结
本题是“移除盒子”的扩展，加入了颜色相关的移除成本。
关键点在于状态定义和转移方程的设计，特别是“左边保留的同色盒子数 k”这一维状态，使得我们可以推迟移除，以积累同色盒子获得更高的平方收益，同时减去对应的成本。