Based off Modern Art 2, although the solution is completely different.

Subtask 2:

We can split the painting into groups of $M=12$ and run $\mathcal{O}(2^Mpoly(M))$ BFS on each group independently. A state consists of a bitmask of length $M$ where the $i$-th bit of the bitmask is equal to one if the $i$-th cell is colored the way that it should be in the final painting, as well as the minimum number of strokes required to reach that bitmask (denoted by $\texttt{dist}$ in the solution below).

To transition from a state, we go through each of the $\mathcal{O}(M^2)$ possible ranges that a stroke can paint over and through each of the $\mathcal{O}(M)$ possible colors for the stroke.

Code (courtesy of Andrew Wang):

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e9;
vector<int> dist;
queue<int> q;

void add(int mask, int distance) { //add new mask to the queue + update distance
	if(dist[mask] != MAX)
		return;
	dist[mask] = distance;
	q.push(mask);
}

int solve(vector<int> v, int lowest_color) {
	int N = v.size();
	dist.assign(1<<N, MAX);
	add(0, 0);
	while (q.size()) {
		int x = q.front(); q.pop();
		for(int color = lowest_color; color < lowest_color+12; color++) {
			//loop through intervals with same beginning + ending color
			for(int i = 0; i < N; i++) {
				if(v[i] == color) {
					for(int j = i; j < N; j++) {
						if(v[j] == color) {
							int cur_mask = x; 
							for(int k = i; k <= j; k++) {
								//if same color, then update the mask as correctly painted
								if (v[k] == color) 
									cur_mask |= 1 << k;
								//if already painted correctly, update it as painted over incorrectly
								else if (cur_mask & (1<<k)) 
									cur_mask ^= 1 << k;
							}
							add(cur_mask, dist[x]+1);
						}
					}
				}
			}
		}
	}
	return dist[(1<<N)-1];
}

int main() {
	cin.tie(0)->sync_with_stdio(0); 
	int N; cin >> N;
	vector<int> cur_batch;
	int ans = 0;
	for(int i = 0; 12*i < N; i++) { //breaking it up in batches of size <= 12
		for(int j = 12*i; j < 12*(i+1) && j < N; j++) {
			int a; cin >> a;
			cur_batch.push_back(a);
		}
		ans += solve(cur_batch, 12*i+1);
		cur_batch.clear();
	}
	cout << ans << endl;
}

Full Solution:

Given an optimal way to paint, draw a segment between two distinct cells if they were last painted by the same stroke $x$ and none of the cells in between them were last painted by stroke $x$. The number of strokes required is equal to $N$ minus the number of such segments. For example, we can draw at most five segments for the following test case,

11
1 2 3 4 1 4 3 2 1 1 6

so the number of strokes required is $11-5=6$.

        1
      4---4
    3-------3
  2-----------2
1---------------1-1 6

So we've reduced the problem to computing the maximum size of a set of segments satisfying all three of the following properties:

• The endpoint cells of a segment must share the same color.
• If two segments share an endpoint cell, that cell is the only cell they share.
• Otherwise, the range spanned by one segment is strictly contained within the range spanned by the other.

It suffices to do dynamic programming on ranges to compute the maximum possible number of segments. Define $dp[i][j]$ to be the maximum possible number of segments if we only consider the range from cell $i$ to cell $j$ ($0\le i<j<N$).

• If we draw a segment from cell $i$ to cell $j$ (only possible when these cells have the same color), then all remaining segments must be contained within the interval from cell $i+1$ to cell $j-1$. This gives the transition $dp[i][j]=\max(dp[i][j],1+dp[i+1][j-1])$.
• Otherwise, there must exist some $i<k<j$ such that no segment crosses over cell $k$. This gives the transition $dp[i][j]=\max_{i<k<j}(dp[i][j],dp[i][k]+dp[k][j])$.

Time Complexity: $\mathcal{O}(N^3)$

My code follows:

#include <bits/stdc++.h>
using namespace std;
 
int N, dp[305][305];
 
int main() {
	cin >> N;
	vector<int> a(N); 
	for (int& t: a) cin >> t;
	for (int i = N-1; i >= 0; --i) 
		for (int j = i+1; j < N; ++j) {
			if (a[i] == a[j]) // draw segment from i to j
				dp[i][j] = max(dp[i][j],1+dp[i+1][j-1]);
			for (int k = i+1; k < j; ++k) // split at k
				dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]);
		}
	cout << N-dp[0][N-1] << "\n";
}