看到有区间操作，结合 \(n\le 100\) 的数据范围，直接考虑区间 dp。
设 \(f_{l,r,x}\) 表示将区间 \([l,r]\) 全部替换成 \(x\) 的最小步数。
首先有 \(f_{l,r,x}=\max_{p=l}^{r-1}f_{l,p,x}+f_{p+1,r,x}\)，但这无法将该状态下的所有的情况都转移到，所以考虑再设一个 \(g_{l,r,x}\) 表示将区间 \([l,r]\) 的所有 \(x\) 全部消除的最小步数，则存在转移 \(f_{l,r,x}= g_{l,r,x}+1\)，表示将不存在 \(x\) 的区间 \([l,r]\) 通过一次操作全部替换成 \(x\)。
接下来考虑转移 \(g\)，显然仍有 \(g_{l,r,x}=\max_{p=l}^{r-1}g_{l,p,x}+g_{p+1,r,x}\)。类似 \(f\) 地，\(g\) 也存在转移 \(g_{l,r,x}= f_{l,r,k}(k\not=x)\)。
但是发现 \(f_{l,r,x}\leftarrow g_{l,r,x}\leftarrow f_{l,r,k}(k\not =x)\leftarrow g_{l,r,k}\leftarrow f_{l,r,x}(x\not=k)\)，dp 状态之间的转移出现环形关系，无法直接递推。
We have to either somehow deal with them, or get rid of them. 我们要么以某种关系处理它们，要么把它们去掉。——官方题解
我们不能像 P3232 [HNOI2013] 游走 一样采取第一种办法，所以这里我们采取第二种办法。
考虑裁剪掉一些对答案必然无影响的点，体现在该题中就是：
- 转移 \(f\) 时将左右端点上 \(a_i=x\) 的连续段删掉。即，将 \(l\) 移动到其后第一个 \(a_i\not=x\) 的 \(i\)，将 \(r\) 移动到其前第一个 \(a_i\not=x\) 的 \(i\)。
- 转移 \(g\) 时将左右端点上 \(a_i\not=x\) 的连续段删掉。即，将 \(l\) 移动到其后第一个 \(a_i=x\) 的 \(i\)，将 \(r\) 移动到其前第一个 \(a_i=x\) 的 \(i\)。
考虑当 \(a_l=x\) 时会在转移 \(f\) 时被删掉，否则会在转移 \(g\) 的时候被删掉。此时转移 \(f_{l,r,x}\) 时转移到该状态的 \(g_{l',r',x}\) 的 \([l',r']\not=[l,r]\)，由此证明了这样不会导致它们之间的转移关系成环。
这种转移式子显然是没法递推的，所以要用记搜。
时间复杂度 \(O(n^4)\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define FlushIn fread(ibuf,1,1<<25,stdin)
#define FlushOut fwrite(obuf,1,oh-obuf,stdout)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=d)
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
bool smallingll(long long x,long long y){return x<y;}
namespace FastIO{
char ibuf[1<<25],*ih=ibuf,obuf[1<<25],*oh=obuf;
inline int rd(){
int x=0;for(;!isdigit(*ih);++ih);
for(x=0;isdigit(*ih);x=x*10+*ih++-48);return x;
}
inline void write(int x){
if(x==0)return void(*oh++='0');
static int buf[30],xb;
for(xb=0;x;x/=10)buf[++xb]=x%10;
for(;xb;)*oh++=buf[xb--]|48;
}
}//using namespace FastIO;
namespace NormalIO{
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
}using namespace NormalIO;
bool Mbg;
const int maxn=105,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m,a[maxn];
int f[maxn][maxn][maxn],g[maxn][maxn][maxn];
int pre[2][maxn][maxn],sec[2][maxn][maxn];
//0 =/1 !=
int bfs(int l,int r,int x);
int dfs(int l,int r,int x){
l=sec[1][l][x],r=pre[1][r][x];
if(l>r)return 0;
if(f[l][r][x]!=-1)return f[l][r][x];
int res=inf;
rep(p,l,r-1)res=min(res,dfs(l,p,x)+dfs(p+1,r,x));
res=min(res,bfs(l,r,x)+1);
return f[l][r][x]=res;
}
int bfs(int l,int r,int x){
l=sec[0][l][x],r=pre[0][r][x];
if(l>r)return 0;
if(g[l][r][x]!=-1)return g[l][r][x];
int res=inf;
rep(p,l,r-1)res=min(res,bfs(l,p,x)+bfs(p+1,r,x));
rep(i,1,m)if(i^x)res=min(res,dfs(l,r,i));
return g[l][r][x]=res;
}
void init(){
rep(j,1,m){
pre[0][0][j]=pre[1][0][j]=0;
rep(i,1,n){
if(a[i]==j)pre[0][i][j]=i,pre[1][i][j]=pre[1][i-1][j];
else pre[0][i][j]=pre[0][i-1][j],pre[1][i][j]=i;
}
sec[0][n+1][j]=sec[1][n+1][j]=n+1;
per(i,n,1){
if(a[i]==j)sec[0][i][j]=i,sec[1][i][j]=sec[1][i+1][j];
else sec[0][i][j]=sec[0][i+1][j],sec[1][i][j]=i;
}
}
}
void solve_the_problem(){
n=rd(),m=rd();rep(i,1,n)a[i]=rd();
mem(f,-1),mem(g,-1);init();
int ans=inf;
rep(i,1,m)ans=min(ans,dfs(1,n,i));
write(ans,10);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=rd();while(_--)solve_the_problem();
}