Solução Informática - Nível Avançado - Semana 5

Solução por Lúcio Figueiredo

Conhecimento prévio necessário:

• Programação Dinâmica
• Somas de Prefixo

Vamos utilizar programação dinâmica para resolver o problema. Seja $dp[l][r]$ o menor custo possível para juntar todos os bolinhos de índices entre $l$ e $r$ $(l \leq r)$.

Vamos analisar a última operação realizada no intervalo $[l...r]$, ou seja, a operação que transformou este intervalo em um bolinho só. É possível observar que esta última operação juntou dois sub-intervalos de $[l...r]$ em um intervalo só, isto é, a última operação no intervalo juntou os sub-intervalos $[l...i]$ e $[i+1...r]$ em um só, para algum $i$ no intervalo $[l...r-1]$.

Ainda precisamos descobrir como calcular o custo da operação de juntar o intervalo $[l...i]$ com o intervalo $[i+1...r]$. Para fazer isso, note que o valor de um intervalo $[l...r]$ qualquer, ou seja, o valor de um bolinho de queijo resultante ao juntar todos os bolinhos em $[l...r]$, é exatamente $\sum_{k=l}^r a_k$.

Logo, o custo total de juntar os intervalos $[l...i]$ e $[i+1...r]$ de modo a formarem um único bolinho $[l...r]$ é $dp[l][i] + dp[i+1][r] + \sum_{k=l}^r a_k$, ou seja, a soma dos custos de transformar $[l...i]$ e $[i+1...r]$ em um bolinho único e, por fim, o custo de juntar tais dois bolinhos.

Assim, quando calcularmos $dp[l][r]$, podemos iterar por cada $i$ de $l$ a $r-1$, calculando assim o menor custo possível para juntar os bolinhos em $[l...r]$. Como podemos calcular a soma de um intervalo qualquer em $O(1)$ (utilizando Soma de Prefixos), a complexidade final da solução é $O(n^3)$, pois rodamos um loop em $O(n)$ para cada um dos $O(n^2)$ estados da programação dinâmica. Por fim, a resposta do problema é $dp[1][n]$.

Confira o código abaixo para melhor entendimento: