题目描述

你们中的一些人可能玩过一个叫做消木块的游戏。

$n$ 个木块排成一列，每个木块都有一个颜色。

每次，你都可以点击一个木块，这样被点击的木块以及和它相邻并且同色的木块就会消除。

如果一次性消除了 $k$ 个木块，那么就会得到 $k \times k$ 分。

给定你一个游戏初始状态，请你求出最高得分是多少。

输入格式

第一行包含整数 $t$，表示共有 $t$ 组测试数据。

每组数据第一行包含整数 $n$，表示共有 $n$ 个木块。

第二行包含 $n$ 个整数，表示 $n$ 个木块的颜色。

代表木块颜色的整数范围是 $1 \sim n$。

输出格式

每组数据输出一个结果，每个结果占一行。

输出格式为 Case x: y，其中 $x$ 为数据组别编号，从 $1$ 开始，$y$ 为结果。

样例

2
9
1 2 2 2 2 3 3 3 1
1
1

Case 1: 29
Case 2: 1

样例解释

第一组数据

$n=9$ 颜色序列：1 2 2 2 2 3 3 3 1

最优消除顺序

一种最优方案：

1. 点击第 5 个木块（颜色 2），消除四个连续的 2（位置 2~5），得到 $4 \times 4 = 16$ 分。序列变为 1 3 3 3 1。
2. 点击第 2 个木块（颜色 3），消除三个连续的 3（位置 2~4），得到 $3 \times 3 = 9$ 分。序列变为 1 1。
3. 点击第 1 个木块（颜色 1），消除两个连续的 1，得到 $2 \times 2 = 4$ 分。总分 $16+9+4=29$。

输出 Case 1: 29

第二组数据

$n=1$，颜色 1，只能消除这一个，得分 $1 \times 1 = 1$。

输出 Case 2: 1

数据范围

• $1 \le n \le 200$
• 颜色范围为 $1 \sim n$

算法分析

这是一个区间动态规划问题，类似于“消除游戏”或“方块消除”。

难点

消除一个区间后，两边可能合并（如果颜色相同），从而产生连锁消除。因此不能简单地枚举消除顺序。

状态定义

设 $dp[l][r][k]$ 表示考虑区间 $[l, r]$，并且在该区间右侧有 $k$ 个与 $a[r]$ 颜色相同的木块紧跟着（即这 $k$ 个木块在原序列中位置在 $r$ 之后，但在消除过程中可能由于左边消除而合并过来），将这些木块一起消除所能获得的最大分数。

解释：$k$ 表示在区间 $[l, r]$ 之后还有 $k$ 个与 $a[r]$ 同色的木块，它们可以和在 $[l, r]$ 中的某些同色木块一起消除。这样定义是为了处理合并消除。

转移方程

考虑区间 $[l, r]$，以及右边额外的 $k$ 个与 $a[r]$ 同色的木块。

1. 直接消除：将 $[l, r]$ 连同右边 $k$ 个木块一起消除，得分 = $(len + k)^2$，其中 $len$ 是区间 $[l, r]$ 中与 $a[r]$ 同色的连续段的长度。但 $len$ 需要计算。

   实际上，我们可以先找到区间 $[l, r]$ 中从 $r$ 向左连续与 $a[r]$ 同色的木块个数，设 $p$ 为最左位置满足 $a[p] = a[r]$ 且 $a[p..r]$ 颜色相同。那么 $len = r - p + 1$。

   然后直接消除得分 = $(len + k)^2 + dp[l][p-1][0]$（因为 $[p, r]$ 连同右边 $k$ 个被消除，剩下 $[l, p-1]$ 单独处理）。

2. 不直接消除，先消除中间部分：枚举一个分割点 $i$（$l \le i < r$），使得 $a[i] = a[r]$，并且先消除 $[i+1, r-1]$，然后 $a[i]$ 就会和 $a[r]$ 以及右边 $k$ 个木块合并。那么：

   $$dp[l][r][k] = \max_{l \le i < r, a[i] = a[r]} \{ dp[l][i][len + k] + dp[i+1][r-1][0] \}$$

   其中 $len$ 是 $[i, r]$ 中与 $a[r]$ 同色的连续段长度？实际上 $len$ 应该是 $[i, r]$ 中与 $a[r]$ 同色的木块个数，但因为我们只考虑 $a[i] = a[r]$，所以 $len$ 至少为 2。但更准确地说，$dp[l][i][len + k]$ 中的 $len$ 是 $[i, r]$ 中与 $a[r]$ 同色的木块个数（包括 $i$ 和 $r$ 以及中间的相同颜色），但 $dp[i+1][r-1][0]$ 已经处理了中间部分。

   实际上，我们通常这样转移：在区间 $[l, r]$ 中，找到一个位置 $i$，使得 $a[i] = a[r]$，且 $i$ 不是 $r$。我们先消除 $[i+1, r-1]$，得到分数 $dp[i+1][r-1][0]$，然后 $a[i]$ 就和 $a[r]$ 以及右边 $k$ 个木块连在一起，相当于 $dp[l][i][k+1]$（因为现在 $a[i]$ 右边有 $k+1$ 个同色木块，包括 $a[r]$ 和右边的 $k$ 个）。但注意 $a[i]$ 和 $a[r]$ 之间可能还有其他同色木块，所以实际上 $a[i]$ 右边有 $(r-i) + k$ 个同色木块？不对，因为 $[i+1, r-1]$ 中可能也有同色木块，但我们已经先消除了，所以剩下的只有 $a[r]$ 和右边 $k$ 个。

   因此，更常见的转移是：

   $$dp[l][r][k] = \max(dp[l][r-1][0] + (1+k)^2, \max_{l \le i < r-1, a[i] = a[r]} \{ dp[l][i][k+1] + dp[i+1][r-1][0] \})$$

   但这种转移可能不够完备。

常见题解

本题是经典题“Blocks”（UVA 10559），标准解法是：

设 $dp[l][r][k]$ 表示区间 $[l, r]$，且 $r$ 后面有 $k$ 个与 $a[r]$ 同色的木块（这些木块在原始序列中位置在 $r$ 之后，但可以通过消除中间部分合并过来）时，能获得的最大分数。

转移：

1. 直接消除 $r$ 及其后面的 $k$ 个：先找到 $[l, r]$ 中从 $r$ 向左连续同色的最左位置 $p$（即 $a[p] = a[r]$ 且 $a[p..r]$ 颜色相同），则消除这些得分为 $(r-p+1 + k)^2 + dp[l][p-1][0]$。
2. 不直接消除，先消除中间部分使 $r$ 与左边同色块合并：枚举 $i$ 从 $l$ 到 $r-1$，如果 $a[i] = a[r]$，则可以先消除 $[i+1][r-1]$，然后 $a[i]$ 与 $a[r]$ 以及右边 $k$ 个合并，即 $dp[l][r][k] = \max(dp[l][r][k], dp[l][i][k+1] + dp[i+1][r-1][0])$。

初始化

$dp[i][i][k] = (1+k)^2$。

最终答案

$dp[1][n][0]$。

复杂度

状态数 $O(n^3)$（$l,r,k$ 各 $n$），转移 $O(n)$，总 $O(n^4)$，对于 $n=200$ 太大（$200^4=1.6\times 10^9$）。

优化：实际上 $k$ 不超过 $n$，但转移时 $k$ 可以减小。可以通过记忆化搜索实现，实际运行状态较少。

另一种优化：$k$ 表示右边同色木块数量，最多为 $n$，但我们可以用 $dp[l][r][k]$ 中 $k$ 表示 $r$ 之后有 $k$ 个与 $a[r]$ 同色的木块，但实际上 $k$ 不会太大，因为原序列中连续同色段有限。但最坏情况可能为 $n$。

通常的优化是：将连续同色的木块合并成一个块，记录颜色和长度，然后 DP。但本题 $n \le 200$，$O(n^4)$ 可能勉强可过（$200^4=1.6\times 10^9$ 太大），需要优化。

实际上，常见题解使用 $O(n^3)$ 的 DP：$dp[l][r][k]$ 表示区间 $[l, r]$ 加上右边 $k$ 个与 $a[r]$ 同色的木块。转移时，枚举 $i$ 使得 $a[i]=a[r]$，先消除 $[i+1, r-1]$，然后 $a[i]$ 与右边合并。这样转移是 $O(n)$ 的，状态 $O(n^2 \cdot n)$，总 $O(n^4)$。但通过优化，可以做到 $O(n^3)$：对于每个 $l,r$，$k$ 最多为 $n$，但转移时 $k$ 的变化是连续的。

实现方法（记忆化搜索）

1. 预处理每个位置 $i$ 向左连续同色的长度 $len[i]$，以及最左位置 $left[i]$。
2. 定义 $dfs(l, r, k)$ 计算 $dp[l][r][k]$。
   • 如果 $l > r$ 返回 0。
   • 如果 $l == r$ 返回 $(1+k)^2$。
   • 否则： a. 直接消除：$p = left[r]$（如果 $p < l$ 则 $p = l$？不对，$left[r]$ 是从 $r$ 向左连续同色的最左位置，可能小于 $l$）。实际上，我们需要在 $[l, r]$ 内找到从 $r$ 向左连续同色的最左位置 $p$，满足 $a[p..r]$ 同色且 $p \ge l$。可以预处理 $next[i]$ 表示从 $i$ 向左第一个不同色的位置。 设 $len = r - p + 1$，则得分 = $(len + k)^2 + dfs(l, p-1, 0)$。 b. 枚举 $i$ 从 $l$ 到 $r-1$，如果 $a[i] == a[r]$，则得分 = $dfs(l, i, k+1) + dfs(i+1, r-1, 0)$。 取最大值。

这样记忆化搜索，状态数 $O(n^3)$，每个状态转移 $O(n)$，总 $O(n^4)$。但实际运行可能较快。

总结

本题是较难的区间 DP，需要处理合并消除。标准解法是定义 $dp[l][r][k]$ 状态，并采用记忆化搜索实现。由于 $n \le 200$，$O(n^4)$ 可能超时，需要使用优化（如预处理连续段）或更高效的转移。