Cities

题意：把一段相同的形状变成其它任意一个形状，需要使用一次魔法，问最少使用多少魔法能使全是同一个形状。

思路：
先把连续的缩成一个连续段，假设缩点后有m个段，如果每个互不相同，答案显然是m-1，不管怎样合都对答案没有影响。如果在合并两个区间时，两个区间的左、右端点的值相同，那么可以通过将中间的值赋值成该值，可以省去一步。
假设表示合并区间的最小代价，表示与相同的点的下标。枚举有没有参与省去的过程，即。同时注意考虑一下左端点相同的情况：

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7,maxm=2e5+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[5001],f[5001][5001],u[5001],lt[5001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n;
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1;i<=n;++i) {
            cin>>a[i];
            if(a[i]==a[i-1]) --i,--n;
            u[a[i]]=0;
        }
        for(int i=1;i<=n;++i) {
            lt[i]=u[a[i]];
            u[a[i]]=i;
            f[i][i]=0;
        }
        for(int len=2;len<=n;++len)
        for(int l=1,r=l+len-1;l<=n-len+1;++l,++r) {
            f[l][r]=f[l][r-1]+1;
            for(int k=lt[r];k>=l;k=lt[k])
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
        }
        cout<<f[1][n]<<'\n';
    }
    return 0;;
}