1922F - Replace on Segment - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define oo 1000000010
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)

const int N = 110;

int n , x , arr[N];

int dp1[N][N][N]; //all equal to k
int dp2[N][N][N]; //nothing equal to k

int sum[N][N];

int good[N];

inline bool has(int l,int r,int k){
	return sum[r + 1][k] > sum[l][k];
}

inline bool all(int l,int r,int k){
	return ((sum[r + 1][k] - sum[l][k]) == (r - l + 1));
}

void solve(){
	scanf("%d%d",&n,&x);
	for(int i = 0 ;i < n;i++){
		scanf("%d",&arr[i]);
		for(int j = 1;j <= x;j++){
			sum[i + 1][j] = sum[i][j] + (arr[i] == j ? 1 : 0);
		}
	}
	if(x == 1){
		puts("0");
		return;
	}

	for(int all , i = 0 ;i < n;i++){
		vector< int > frq(x + 1 , 0);
		all = 0;
		for(int j = i ;j < n;j++){
			if(++frq[arr[j]] == 1) if(++all == x) break;
			good[i] = j;
		}
	}
	for(int l = n - 1;l >= 0;l--){
		for(int k = 1;k <= x;k++){
			dp1[l][l][k] = (arr[l] == k ? 0 : 1);
			dp2[l][l][k] = (dp1[l][l][k] ^ 1);
		}
		for(int mnk = 0 , counter = 0 ,r = l + 1;r < n;r++){
			mnk = 1;
			counter = 0;
			for(int k = 1; k <= x;k++){
				dp2[l][r][k] = dp1[l][r][k] = oo;
				if(good[l] >= r)
					dp2[l][r][k] = 1;
				if(!has(l , r , k)){
					dp2[l][r][k] = 0;
					dp1[l][r][k] = 1;
				}
				if(all(l , r , k))
					dp1[l][r][k] = 0;

				for(int i = l;i < r;i++){
					dp2[l][r][k] = min(dp2[l][r][k] , dp2[l][i][k] + dp2[i + 1][r][k]);
					dp1[l][r][k] = min(dp1[l][r][k] , dp1[l][i][k] + dp1[i + 1][r][k]);
				}
				dp1[l][r][k] = min(dp1[l][r][k] , dp2[l][r][k] + 1);
				dp2[l][r][k] = min(dp2[l][r][k] , dp1[l][r][k] + 1);

				if(dp1[l][r][k] < dp1[l][r][mnk]){
					mnk = k;
					counter = 1;
				}
				else if(dp1[l][r][k] == dp1[l][r][mnk])
					counter++;
			}
			for(int k = 1; k <= x;k++){
				if(counter == 1 && k == mnk) continue;
				dp2[l][r][k] = min(dp2[l][r][k] , dp1[l][r][mnk]);
				dp1[l][r][k] = min(dp1[l][r][k] , dp2[l][r][k] + 1);
			}

		}
	}
	int ans = oo;
	for(int i = 1;i <= x;i++)
		ans = min(ans , dp1[0][n - 1][i]);
	printf("%d\n",ans);
}

int main(){
	
	int t;
	scanf("%d",&t);
	while(t--)
		solve();
	return 0;
}