Combinando Plastilinas

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
C, C++, Java, Lua, Pascal, Python

Hay \(n\) bolas de plastilina de varios tamaños en una fila. Usted desea formar la mayor bola de plastilina posible desarrollando las siguientes operaciones:

• Si dos bolas adyacentes tienen el mismo tamaño, entonces puede combinarlas y hacer una nueva bola. El tamaño de la nueva bola es la suma de los tamaños de las dos bolas viejas. Esta ocupa la posición previamente ocupada por las dos bolas viejas.

• Si dos bolas tienen el mismo tamaño y hay exactamente una bola entre ellas, entonces puede combinar estas tres bolas para hacer una nueva bola de plastilina (la bola del medio no necesita ser del mismo tamaño que las otras dos). El tamaño de la nueva bola es la suma de los tamaños de las tres bolas viejas. Esta ocupa la posición previamente ocupada por las tres bolas viejas.

Usted puede desarrollar cada operación las veces que desee. Determine el tamaño de la mayor bola de plastilina después de desarrolladas 0 o más operaciones.

Entrada

La primera línea contiene el entero, \(n (1 \leq n \leq 400)\). La próxima línea contiene \(n\) enteros separados por espacio representando los tamaños de las bolas de plastilina desde izquierda a derecha. Cada entero es al menos \(1\) y a lo sumo \(1000000\).

Salida

Imprima el tamaño de la mayor bola de plastilina que usted puede formar.

Ejemplo #1 de Entrada

7
47 12 12 3 9 9 3

Ejemplo #1 de Salida

48

Ejemplo #2 de Entrada

4
1 2 3 1

Ejemplo #2 de Salida

3

Explicación del ejemplo 1: Un posible conjunto de movimientos para crear una bola de tamaño \(48\) es combinar \(12\) y \(12\) para formar una bola de tamaño \(24\),entonces combinar \(9\) y \(9\) para formar una de tamaño \(18\), luego se combinan \(3\), \(18\) y \(3\) y se forma una de tamaño \(24\). Finalmente combinamos las dos bolas de tamaño \(24\) y formamos la de tamaño \(48\).

Explicación del ejemplo 2: No hay posibles movimientos así que la de mayor tamaño es \(3\).


Comments


  • 1
    PedroPabloAB  commented on April 10, 2021, 7:42 p.m.

    Así mismo es. De verdad que el usuario aniervs da unas explicaciones geniales, muchas gracias por querer compartir tus conocimientos y ayudarnos a aprender más.👍


  • 3
    Osnielfc_07  commented on April 8, 2021, 7:30 a.m.

    Con el paso del tiempo me he dado cuenta que el 99% de los comentarios que hace el usuaio : //aniervs// sobre la solucion de un problema deberian ser añadidos como editorial para el problema.


  • 3
    Bryanm  commented on Nov. 7, 2019, 3:09 p.m.

    alguien podria decirme q tipo de DP podria aplicar en este problema


    • 3
      aniervs  commented on April 2, 2021, 11:50 p.m. edit 2

      Una plastilina representa a un subrango contiguo del arreglo original, y su valor es igual a la suma de dicho subrango. Entonces, la respuesta es la suma de un rango contiguo del arreglo original.

      Solo necesitamos saber cuáles son los rangos que pueden resultar en una sola plastilina (llamémoslos buenos). Eso lo podemos saber con programación dinámica.

      Digamos que \(dp(l, r)\) nos dice si el rango \([l; r]\) es \(bueno\). Obviamente, los rangos de tamaño \(1\) son buenos, es decir, \(dp(i, i) = true\) para todo \(i\in [1, n]\). Veamos cómo saberlo para rangos de longitud mayor que \(1\).

      Para poder obtener el rango \([l, r]\) como una sola plastilina podíamos:

      • Haber hecho la primera operación con el rango \([l, k]\) y el rango \([k + 1, r]\) para algún \(k \in [l, r-1]\). Podemos elegir un \(k\) si el rango \([l, k]\) es bueno, el rango \([k + 1, r]\) es bueno, y además la suma del rango \([l; k]\) es igual a la suma del rango \([k + 1, r]\).

      • Haber hecho la segunda operación con el rango \([l, a-1]\), el rango \([a, b]\) y el rango \([b + 1, r]\) para algún par \(a, b: l < a\le b< r\). El rango \([a, b]\) representa la plastilina intermedia, y los rangos \([l, a-1]\) y \([b + 1, r]\) serían las plastilinas de igual tamaño. Podemos elegir un rango \([a, b]\) si \([a, b]\), \([l, a-1]\) y \([b + 1, r]\) son los tres buenos, y además la suma del rango \([l,a-1]\) es igual a la suma del rango \([b + 1, r]\).

      \[dp(l, r) = \left[\bigvee_{a=l}^{r-1}\bigvee_{b=a}^{r-1} dp(l, a-1)\land dp(a,b)\land dp(b+1,r)\land sum(l,a-1)=sum(b+1,r)\right] \vee \left[\bigvee_{k=l}^{r-1}dp(l, k)\land dp(k+1,r)\land sum(l,k)=sum(k+1,r)\right]\]

      El operador \(\vee\) denota el or-inclusivo (|| en C++), y el operador \(\land\) denota el and (&& en C++).

      Código de ejemplo:

          for(int i = 1; i <= n; i++)
              dp[i][i] = 1;
      
          for(int t = 2; t <= n; t++){
              for(int i = 1; i + t - 1 <= n; i++){
      
                  int j = i + t - 1;
      
                  for(int k = i; k < j; k++){
                      dp[i][j] |= dp[i][k] and dp[k + 1][j] and sum(i, k) == sum(k + 1, j);
                  }
      
                  for(int a = i; a < j; a++)
                      for(int b = a; b < j; b++){
                          dp[i][j] |= dp[i][a - 1] and dp[b + 1][j] and dp[a][b] and sum(i, a - 1) == sum(b + 1, j);
                      }
      
              }
          }
      

      Ahora, esa solución tiene complejidad temporal \(\mathcal{O}(n^4)\); hay que optimizarla. La parte que necesitamos cambiar es cómo iteramos por los pares \(a, b\).

      Supongamos que \(l, r\) están fijos, a medida que aumentamos \(a\), la suma del rango \([l, a-1]\) aumenta (ya que los elementos del arreglo son positivos). Y a medida que aumentamos \(b\), la suma del rango \([b + 1, r]\) disminuye. Como queremos que \(sum(l, a-1) = sum(b + 1, r)\), si aumentamos \(a\), entonces \(b\) no puede aumentar. Podemos, en lugar de iterar por todos los pares \(a, b\), llevar dos punteros: \(a\) inicia en \(l + 1\), y \(b\) inicia en \(r - 1\). \(a\) se mueve de \(1\) en \(1\) hacia la derecha, y cada vez que \(a\) se mueva un paso, movemos \(b\) a la izquierda mientras \(a < b\) y \(sum(l, a - 1) > sum(b + 1, j)\).

      Una vez que \(b\) se movió todo lo requerido, y si \(a \le b\), usamos la misma fórmula.

      Como para \(l, r\) fijos, \(a\) solo se mueve hacia la derecha, y \(b\) a la izquierda, cada posición del rango \([l, r]\) es visitada una vez por \(a\), y una vez por \(b\). Por tanto, para \(l, r\) fijos, se hacen \(O(r - l + 1)\) iteraciones. Eso quiere decir que la complejidad temporal ahora es \(O(n^3)\).