题目内容

小塔有一个长度为$n$的数组［$a1，a2，..，an$］，他希望将数组切分为若干段，使得每一段的$MEX$求和尽可能大。 数组的$MEX$定义为没有出现在数组中的最小非负整数，例如，$MEX[1,2,3]=0$,$MEX[1,0,3] =2$

考虑$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])表示新开一个区间