248

Solución en video

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++.

Explicación

Consideremos un rango $A[i..j]$ . Como los elementos necesitan ser adyacentes para fusionarse y cada nuevo elemento se originará de una serie de fusiones sobre un subarreglo, podemos pensar en los subarreglos de $A[i..j]$ .

Definamos $dp[i][j]$ como el subarreglo de $A$ (con $i$ y $j$ inclusivos e indexados desde cero) tal que $dp[i][j]$ es el elemento en el que se puede fusionar como un único elemento. Si no se puede fusionar en un único elemento, sea $-1$ . Para $k$ desde $i$ hasta $j-1$ inclusive, podemos comprobar las siguientes transiciones:

Si $i == j$ , $dp[i][j] = a[i]$ (caso base).
En caso contrario, si $dp[i][k] \neq -1$ y $dp[i][k] == dp[k+1][j]$ , entonces $dp[i][j] = dp[i][k] + 1$ .

Si encontramos dos rangos iguales y adyacentes, podemos fusionarlos por un valor de $1$ más el valor de cualquiera de los dos rangos. También puede ser útil notar que un rango solo puede fusionarse en un número único. Por lo tanto, no es necesario escribir las transiciones como $dp[i][j] = \max(dp[i][j], dp[i][k] + 1)$ .

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	freopen("248.in", "r", stdin);
	int n;
	cin >> n;
 
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
 
	// dp[i][j] = elemento final en el que se fusiona el rango i..j,
	// de lo contrario es -1 si no se puede fusionar en un único elemento
	vector<vector<int>> dp(n, vector<int>(n, -1));
 
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		dp[i][i] = a[i];
		for (int j = i; j < n; j++) {
			for (int k = i; k < j; k++) {
				if (dp[i][k] != -1 and dp[i][k] == dp[k + 1][j]) {
					dp[i][j] = dp[i][k] + 1;
				}
			}
			ans = max(ans, dp[i][j]);
		}
	}
 
	freopen("248.out", "w", stdout);
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class U248 {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("248");
 
		int N = io.nextInt();
		int[] board = new int[N];
 
		int[][] dp = new int[N][N];
		for (int i = 0; i < N; i++) {
			board[i] = io.nextInt();
			dp[i][i] = board[i];
		}
 
		int max_val = 0;
		for (int i = N - 1; i >= 0; i--) {
			for (int j = i; j < N; j++) {
				for (int k = i; k < j; k++) {
					if (dp[i][k] == dp[k + 1][j] && dp[i][k] != 0) {
						dp[i][j] = dp[i][k] + 1;
					}
				}
 
				max_val = Math.max(max_val, dp[i][j]);
			}
		}
 
		io.println(max_val);
		io.close();
	}
 
	// CodeSnip{Kattio}
}