Matcom Online Grader
Solución al problema 6066 - Array by jc 6 years, 11 months ago
Problema
6066 - Array
Solución
La solución usando dp con complejidad $O(nk)$ no funciona debido a los límites del problema. La solución es un poco más sofisticada. Supongamos que $a_i$ es el menor elemento del array. Uno podría asumir que existe una solución óptima en la que seleccionamos $a_i$, pero como es fácil comprobar este no es el caso siempre. Consideremos la situación donde una solución óptima $S$ no contiene al elemento $a_i$; si esta solución no contiene a $a_{i-1}$ o a $a_{i+1}$ entonces podíamos adicionar a $a_i$ a la solución $S$ (para lo cual sería necesario eliminar un elemento en $S$), con lo cual la nueva solución no sería peor que la original. El único caso en el que no podíamos adicionar $a_i$ sería cuando $a_{i-1} \in S$ y $a_{i+1} \in S$. De lo anterior se deduce que $a_i \in S$ o $a_{i-1}, a_{i+1} \in S$. Esto nos permite reducir el problema a una instancia del mismo pero seleccionado $k-1$ elementos, y en el cual los elementos $a_{i-1}, a_i, a_{i+1}$ son eliminados del array y remplazados por un único elemento con valor $a_{i-1}+a_{i+1}-a_i$. Sea $P$ el problema orginal y $P'$ el problema reducido. La solución óptima $P$ con costo $C$ corresponde a alguna solución óptima $P'$ con costo $C - a_i$. Por otro lado, para cualquier solución $P'$ con costo $C$ podemos encontrar una solución óptima $P$ con costo $C+a_i$. Por lo que en lugar de encontrar la solución para $P$ podemos encontrar la solución para $P'$ y adicionarle el valor $a_i$. Para resolver $P'$ podemos aplicar el mismo razonamiento, hasta llegar a una instancia del problema donde $k=0$ o $k=1$, en el cual la solución óptima es $0$ o el menor elemento del
array
, respectivamente.