外观
数组最大的MEX求和
约 416 字大约 1 分钟
2024-10-13
🌳 题目描述：
题目内容
小羊有一个长度为 n 的数组［a1，a2，..，an］，他希望将数组切分为若干段，使得每一段的 MEX 求和尽可能大。 数组的 MEX 定义为没有出现在数组中的最小非负整数，例如 MEX[1,2,3] = 0， MEX[1,0,3] = 2
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 T (1 ≤ T ≤ 100) 代表数据组数，
每组测试数据描述如下：
第一行输入一个整数 n (1 ≤ n ≤ 2000) 代表数组中的元素数量。
第二行输入 n 个整数 a1，a2，..，an (0 ≤ ai ≤ n) 代表数组元素。除此之外，保证所有的 n 之和不超过2000。
输出描述
在一行上输出一个整数，代表每一段的 MEX 之和。
样例1
输入
2
4
0 1 1 0
6
0 1 1 1 2 3输出
4
4说明
对于第一组测试数据，切分成 [0，1] 和 [1，0] 两个数组，能得到求和的最大答案。由于MEX0，MEX1 都等于 2，答案为 4,
🕵🏽 面试评估：
这道题主要考察区间划分型动态规划，需要将数组划分成若干个子段，每个子段的 MEX 值尽量大。这要求候选人不仅要能够理解 MEX 概念，还要能够设计合理的划分策略，总体难度偏上。
🧗难度系数：
⭐️ ⭐️ ⭐️ ⭐️ ⭐️