考虑$dp[i][j]$表示最后一个为$j$,最后一段区间从$j$开始的最大$MEX$和,$g[i][j]$表示区间$(i,j)$的$MEX$那么转移分为两种: 第一种

dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - g[j][i] + g[j][i + 1]) 表示延续当前区间

第二种

dp[i+1][i+1]=max(dp[i+1][i+1],dp[i][j]+g[i+1][i+1])表示新开一个区间

c++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010; 
int n, a[N], dp[N][N], temp[N], g[N][N]; 

void solve() {
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> a[i]; 

    // 计算 g[i][j]：表示从 i 到 j 的mex
    for (int i = 1; i <= n; i++) {
        int p = 0; 
        for (int j = 0; j <= n; j++) temp[j] = 0; 
        for (int j = i; j <= n; j++) {
            temp[a[j]] = 1; 
            while (temp[p]) p++; 
            g[i][j] = p; 
        }
    }


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = -1;

    dp[1][1] = g[1][1]; 

    
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= i; j++)
            if (dp[i][j] != -1) {
                // 延续dp[i+1][j]
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - g[j][i] + g[j][i + 1]);
                // 新开dp[i+1][i+1]
                dp[i + 1][i + 1] = max(dp[i + 1][i + 1], dp[i][j] + g[i + 1][i + 1]);
            }

    int ans = 0; 
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[n][i]); // 计算最大值

    cout << ans << endl; 
}

signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.t

python

def solve():
    n = int(input())  
    a = list(map(int, input().split()))  
    a = [0] + a  

    # 初始化 g 数组，g[i][j] 表示从 i 到 j 的 mex（最小不重复值）
    g = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        p = 0  
        temp = [0] * (n + 1)  
        for j in range(i, n + 1):
            
            if a[j] <= n:
                temp[a[j]] = 1 
            while p <= n and temp[p]:  # 找到当前的 mex 值
                p += 1
            g[i][j] = p  # 记录 g[i][j] 为当前 mex 值

    # 初始化 dp 数组为 -1
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    dp[1][1] = g[1][1]  # 初始化 dp[1][1]

    # 动态规划更新 dp 数组
    for i in range(1, n):
        for j in range(1, i + 1):
            if dp[i][j] != -1:  # 如果 dp[i][j] 有效
                # 更新 dp[i + 1][j]，延续当前状态
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - g[j][i] + g[j][i + 1])
                # 新开 dp[i + 1][i + 1]，表示新增加一个不同的元素
                dp[i + 1][i + 1] = max(dp[i + 1][i + 1], dp[i][j] + g[i + 1][i + 1])

    ans = 0  
    for i in range(1, n + 1):
        ans = max(ans, dp[n][i])  # 计算最大值

    print(ans)  


if __name__ == "__main__":
    t = int(input())  
    for _ in range(t):
        solve()  

java

import java.util.Scanner;

public class Main {
    static final int N = 2010; 
    static int n; 
    static int[] a = new int[N]; 
    static int[][] dp = new int[N][N]; 
    static int[] temp = new int[N]; 
    static int[][] g = new int[N][N]; 

    static void solve(Scanner scanner) {
        n = scanner.nextInt(); 
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt(); 
        }
        
        // 计算 g[i][j]：表示从 i 到 j 的 mex（最小不重复值）
        for (int i = 1; i <= n; i++) {
            int p = 0; // 记录当前 mex 值
            for (int j = 0; j <= n; j++) temp[j] = 0; 
            for (int j = i; j <= n; j++) {
                temp[a[j]] = 1; 
                while (temp[p] == 1) p++; 
                g[i][j] = p; 
            }
        }

        // 初始化 dp 数组为 -1
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = -1;

        dp[1][1] = g[1][1]; 
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (dp[i][j] != -1) { // 如果 dp[i][j] 有效
                    // 更新 dp[i + 1][j]，延续当前状态
                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] - g[j][i] + g[j][i + 1]);
                    // 新开 dp[i + 1][i + 1]，表示新增加一个不同的元素
                    dp[i + 1][i + 1] = Math.max(dp[i + 1][i + 1], dp[i][j] + g[i + 1][i + 1]);
                }
            }
        }

        int ans = 0; 
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dp[n][i]); // 计算最大值
        }
        System.out.println(ans); 
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        int t = scanner.nextInt(); 
        while (t-- > 0) {
            solve(scanner); 
        }
        scanner.close(); 
    }
}

题目内容

小红有一个长度为$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≤a_i≤n)$代表数组元素。 除此之外，保证所有的$n$之和不超过$2000$。

输出描述

在一行上输出一个整数，代表每一段的$MEX$之和。

样例1

输入

2
4
0 1 1 0
6
0 1 1 1 2 3

输出

4
4

说明

对于第一组测试数据，切分成$[0，1]$和$[1，0]$两个数组，由于$MEX{0，1}=2$，所以答案为$4$。可以证明没有更大的答案。