Zuma

Solución

Explicación

En el espíritu de la DP de rangos, definimos $dp[i][j]$ como el número mínimo de deslizamientos necesarios para borrar todas las gemas entre los índices $i$ y $j$ inclusive. Si $i > j$ entonces no hay gemas en el rango y el arreglo devolverá $0$ .

Hay dos situaciones desde las que podemos transicionar.

La primera es más simple: borramos el primer elemento o los dos primeros del arreglo (si son iguales). En este caso, el valor que obtenemos es $dp[i+1][j]+1$ o $dp[i+2][j]+1$ .

El segundo caso es un poco más feo, y al principio puede parecer poco intuitivo:

Si $i + 2 \le k \le j$ y las gemas en las posiciones $i$ y $k$ son del mismo color, entonces podemos actualizar con el siguiente valor candidato:
$> dp[i+1][k-1]+dp[k+1][j] >$

Uno puede preguntarse por qué no hay un deslizamiento extra en esta transición. Después de todo, ¿dónde borramos las gemas $i$ y $k$ ?

La respuesta es que podemos borrarlas junto con el último deslizamiento que eliminó lo que quedaba en $dp[i+1][k-1]$ . Como el último deslizamiento que borró estas gemas era un palíndromo, podemos añadir $i$ y $k$ al inicio y al final sin problemas.

Implementación

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

C++Java


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	vector<int> gems(n);
	for (int i = 0; i < n; ++i) cin >> gems[i];
 
	/*
	 * this[i][j] = mín. deslizamientos para borrar literalmente todo de i a j (inclusive)
	 * el +1 es solo un buffer para algunos accesos a rangos inválidos
	 * (el arreglo siempre devuelve 0 para rangos inválidos)
	 */
	vector<vector<int>> swipes(n + 1, vector<int>(n, 0));
 
	for (int i = 0; i < n; ++i) swipes[i][i] = 1;
 
	for (int len = 2; len <= n; ++len) {
		for (int start = 0; start <= n - len; ++start) {
			int end = start + len - 1;
 
			// tal vez solo hay que borrar un extremo por su cuenta
			swipes[start][end] = 1 + swipes[start + 1][end];
 
			for (int match = start + 2; match <= end; ++match) {
				if (gems[start] == gems[match]) {
					// en este caso el último deslizamiento del rango izquierdo también
					// puede borrar las gemas en start y match
					swipes[start][end] =
					    min(swipes[start][end],
					        swipes[start + 1][match - 1] + swipes[match + 1][end]);
				}
			}
 
			// caso borde para empezar un palíndromo nuevo
			if (gems[start] == gems[start + 1]) {
				swipes[start][end] =
				    min(swipes[start][end], swipes[start + 2][end] + 1);
			}
		}
	}
 
	cout << swipes[0][n - 1] << '\n';
 
	return 0;
}


import java.io.*;
import java.util.Arrays;
 
public class Zuma {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int gemNum = Integer.parseInt(read.readLine());
		int[] gems = Arrays.stream(read.readLine().split(" "))
		                 .mapToInt(Integer::parseInt)
		                 .toArray();
 
		/*
		 * this[i][j] = mín. deslizamientos para borrar literalmente todo de i a j (inclusive)
		 * el +1 es solo un buffer para algunos accesos a rangos inválidos
		 * (el arreglo siempre devuelve 0 para rangos inválidos)
		 */
		int[][] swipes = new int[gemNum + 1][gemNum];
		for (int i = 0; i < gemNum; i++) { swipes[i][i] = 1; }
		for (int len = 2; len <= gemNum; len++) {
			for (int start = 0; start <= gemNum - len; start++) {
				int end = start + len - 1;
 
				// tal vez solo hay que borrar un extremo por su cuenta
				swipes[start][end] = 1 + swipes[start + 1][end];
 
				for (int match = start + 2; match <= end; match++) {
					if (gems[start] == gems[match]) {
						// en este caso el último deslizamiento del rango izquierdo también
						// puede borrar las gemas en start y match
						swipes[start][end] =
						    Math.min(swipes[start][end], swipes[start + 1][match - 1] +
						                                     swipes[match + 1][end]);
					}
				}
 
				// caso borde para empezar un palíndromo nuevo
				if (gems[start] == gems[start + 1]) {
					swipes[start][end] =
					    Math.min(swipes[start][end], swipes[start + 2][end] + 1);
				}
			}
		}
 
		System.out.println(swipes[0][gemNum - 1]);
	}
}