Tenzing and Balls

Análisis oficial (C++) 

Explicación

Podemos empezar notando que todos los rangos que se eliminan deben ser disjuntos. Si dos rangos se solapan, se pueden combinar en un solo segmento. Si un segmento está dentro de otro, entonces el segmento más grande puede reemplazar al más pequeño.

Usando esta idea, el objetivo se puede pensar como el número mínimo de bolas restantes. Definimos $dp[i]$ como el número mínimo de bolas que quedan después de mirar las primeras $i$ bolas.

En la bola $i$, tenemos dos opciones:

• No usarla en ningún segmento, así $dp[i] = dp[i-1] + 1$
• Emparejarla con una bola anterior del mismo color en la posición $k$ y eliminar todas las bolas de $k$ a $i$, así $dp[i] = dp[k-1]$

La fórmula se puede condensar aún más en

donde $\texttt{best}[a_i]$ guarda el valor mínimo de $dp[k-1]$ sobre todas las posiciones anteriores $k$ tales que $a_k = a_i$.

Después de hallar $dp[i]$, actualizamos $\texttt{best}[a_i] = \min(\texttt{best}[a_i], dp[i-1])$.

La respuesta final es $N - dp[N]$.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
 
const int INF = 1e9;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<int> balls(n);
		for (int i = 0; i < n; i++) { cin >> balls[i]; }
 
		vector<int> dp(n + 1, INF);
		dp[0] = 0;
 
		vector<int> best(n + 1, INF);
		for (int i = 1; i <= n; i++) {
			// keep or delete segment ending at index i
			dp[i] = min(dp[i - 1] + 1, best[balls[i - 1]]);
 
			// update best for this color with dp[i-1]
			best[balls[i - 1]] = min(best[balls[i - 1]], dp[i - 1]);
		}
 
		cout << n - dp[n] << '\n';
	}
}

INF = 10**20
 
T = int(input())
for _ in range(T):
	N = int(input())
	balls = list(map(int, input().split()))
	dp = [INF] * (N + 1)
	dp[0] = 0
 
	best = [INF] * (N + 1)
	for i in range(1, N + 1):
		# keep or delete segment ending at index i
		dp[i] = min(dp[i - 1] + 1, best[balls[i - 1]])
		# update best for this color with dp[i-1]
		best[balls[i - 1]] = min(best[balls[i - 1]], dp[i - 1])
 
	print(N - dp[N])