给定一个数组 t ，定义任意数 x 在 t 中的出现次数为 cnt(x) 。称 t 被 v 支配，当且仅当对任意 v' 有 cnt(v)≥ cnt(v') ；若出现次数相同，则取数值最大的那个 v 。定义数组 t 的权值为 v × |t| （其中 |t| 为 t 的长度）。 现在给定一个长度为 n 的数组 a_1,a_2,...,a_n ，你需要将其划分为若干个非空连续子数组，使得各子数组权值之和最小，输出该最小值。 【子数组】子数组为原数组中任意一个连续且非空的元素区间。
输入包含多组测试数据。第一行包含整数 T(1≤ T≤ 10^3) 表示测试组数。每组数据描述如下： 第一行包含一个整数 n(1≤ n≤ 2× 10^3) ； 第二行包含 n 个整数，表示数组 a_1,a_2,...,a_n(-10^9≤ a_i≤ 10^9) 。 保证所有测试中 n 的总和不超过 5× 10^3 。
对于每组测试数据，输出一行一个整数，表示将数组划分为若干非空连续子数组后，权值之和的最小值。
3 5 1 1 2 2 3 3 5 5 5 4 1 2 3 4
8 15 10
考点：前缀和
数据规模 n ≤ 2000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
参考方向：前缀和
预处理前缀和数组，把「区间求和」从 O(n) 降到 O(1)。
思路框架（前缀和 通法 · 非本题专属）
实现要点：开 long long，避免 n 较大时求和溢出。
复杂度：时间 预处理 O(n)，每次查询 O(1) ｜ 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 3 / 5 / 1 1 2 2 3 / 3 / 5 5 5 / 4 / 1 2 3 4 → 输出 8 / 15 / 10
样例一：一种最优划分为 [1,1,2],[2],[3] ，权值分别为 1×3, 2×1, 3×1 ，总和 3+2+3=8 。
样例二：任意划分总和均为 5×3=15 。
样例三：将其划分为单点 [1],[2],[3],[4] ，总和 1+2+3+4=10 。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2026年春招-美团-算法策略岗-第二批笔试。