考虑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])
表示新开一个区间
小红有一个长度为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之和。
输入
2
4
0 1 1 0
6
0 1 1 1 2 3
输出
4
4
说明
对于第一组测试数据,切分成[0,1]和[1,0]两个数组,由于MEX0,1=2,所以答案为4。可以证明没有更大的答案。