题意
给定长度为 \(n\) 的颜色序列 \(a_i\)，每次你可以选择任意长度的连续且颜色相同的一段位置，将其全部变成任意同一种颜色，问你最少总共需要多少次操作才能使得整个序列颜色相同。
限制： 每一种颜色初始时在序列中最多只有 20 个位置（是该种颜色）。
\(n \leq 3000\)。
思路
考虑将区间 \([l,r]\) 内染成同一种颜色，最暴力的办法就是钦定一种颜色，每次选择一个位置染成该颜色，那么最坏情况下需要染 \(r-l\) 次。而如果当前区间的两端颜色相同，那么就可以减少一次染色操作。这启发我们在序列中选取若干个相同颜色的点对，如下图所示：
显然，如果选取的两对点对相交，那么也只能减少一次操作了。
于是题意就转化为了在序列中选取最多不相交的相同颜色点对。可以考虑区间 dp。
令 \(f_{l,r}\) 为在 \([l,r]\) 区间内最多选取的点对数量，得到转移方程：
\[f_{l,r}=\max(f_{l+1,r},\max_{a_k=a_r} )f_{i+1,k-1}+1+f_{k,j} \]这个转移的实质上就是在枚举左端点可以和哪一个点配对，由于一个点可以同时向左和向右配对，所以转移方程里是 \(f_{k,j}\) 而不是 \(f_{k+1,j}\)。
根据题意，区间中满足 \(a_k=a_r\) 的位置不超过 20，所以这样转移的复杂度是正确的。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3030;
int f[N][N],n,a[N];
vector<int>pos[N];
void chkmax(int &a,int b){if(a<b) a=b;}
void solve()
{
scanf("%d",&n);for(int i=1;i<=n;i++) pos[i].clear();
for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]].push_back(i),f[i][i]=0;
for(int len=2;len<=n;len++)
for(int l=1,r=l+len-1;r<=n;l++,r++)
{
f[l][r]=f[l+1][r];
for(auto k:pos[a[l]])
{
if(k<=l) continue;if(k>r) break;
chkmax(f[l][r],f[l+1][k-1]+1+f[k][r]);
//f[k][r]而不是f[k+1][r]，因为可以同时优化l,k,r
}
}
printf("%d\n",n-1-f[1][n]);
}
int main()
{
int T;scanf("%d",&T);while(T--) solve();
return 0;
}