Modern Art 3

Pista 1

Para un segmento de tamaño $2$ , descompongámoslo en dos segmentos de tamaño $1$ . Nótese que si ambos segmentos comparten el mismo valor, entonces el número mínimo de pintadas para pintar este segmento de tamaño $2$ es la suma de los dos segmentos de tamaño $1$ menos $1$ . En caso contrario, es simplemente la suma de esos dos segmentos.

Pista 2

¿Se puede generalizar esta propiedad a cualquier segmento que vaya de $a$ a $b$ ?

Solución

Explicación

Definamos $\texttt{dp}[i][j]$ como el número mínimo de pintadas para pintar el rango $[i, j]$ . Entonces, al combinar los rangos $[i, j], [j + 1, k]$ puede ocurrir una de dos cosas:

$A[i] == A[k]$ . Esto significa que el rango $[i, k]$ tiene un color común en cada extremo. Por lo tanto, podemos “ahorrar” un color al fusionar los dos rangos. $\texttt{dp}[i][k] = \min(\texttt{dp}[i][k], \texttt{dp}[i][j] + \texttt{dp}[j + 1][k] - 1)$
$A[i] \neq A[k]$ . Esto significa que no hay un color común en el extremo. Como no podemos “ahorrar” un color al fusionar los dos intervalos, simplemente los sumamos.

\texttt{dp}[i][k] = \min(\texttt{dp}[i][k], \texttt{dp}[i][j] + \texttt{dp}[j+1][k])

Implementación

Complejidad temporal: $\mathcal{O}(N^3)$

C++Java


// CodeSnip{CPP Short Template}
 
const int MAX_N = 300;
 
int A[MAX_N], dp[MAX_N][MAX_N];
 
int main() {
	setIO();
 
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++) cin >> A[i];
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { dp[i][j] = MAX_N + 1; }
	}
 
	for (int i = 0; i < MAX_N; i++) dp[i][i] = 1;
 
	for (int s = 0; s < n; s++) {
		for (int i = 0; i < n - s; i++) {
			for (int j = i; j < i + s; j++) {
				int k = i + s;
				if (A[i] == A[k]) dp[i][k] = min(dp[i][k], dp[i][j] + dp[j + 1][k] - 1);
				dp[i][k] = min(dp[i][k], dp[i][j] + dp[j + 1][k]);
			}
		}
	}
 
	cout << dp[0][n - 1] << endl;
}


import java.io.*;
import java.util.*;
 
public class ModernArt3 {
	public static final int MAXN = 300;
	public static int[] painting = new int[MAXN];
	// dp[i][j] es el número de movimientos para pintar de i a j.
	public static int[][] dp = new int[MAXN][MAXN];
 
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < N; i++) { painting[i] = Integer.parseInt(st.nextToken()); }
 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) { dp[i][j] = MAXN + 1; }
		}
		for (int i = 0; i < N; i++) { dp[i][i] = 1; }
		for (int s = 0; s < N; s++) {
			for (int i = 0; i < N - s; i++) {
				for (int j = i; j < i + s; j++) {
					int k = i + s;
					// Fusionamos los 2 rangos
					if (painting[i] == painting[k]) {
						dp[i][k] = Math.min(dp[i][k], dp[i][j] + dp[j + 1][k] - 1);
					}
					// Suma de ambas partes
					dp[i][k] = Math.min(dp[i][k], dp[i][j] + dp[j + 1][k]);
				}
			}
		}
		System.out.println(dp[0][N - 1]);
	}
}