Solução por Lúcio Figueiredo
Conhecimento prévio necessário:
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: