Mix and Merge

Let's define:

• $g(l, r)$ as the said cost to reduce $A[l \dots r]$ sub-array to a single element. $g(1, n)$ will be our result for the whole array.

• $f(l, r, z)$ as the cost to shrink $A[l \dots r]$ sub-array to a $z$-sized sub-array, where $z \le r-l+1$.

By definition, $f(l, r, 1) = g(l, r)$.

For a segment $[l, r]$ and $l \le p < r$, we can pretend that $[l, p]$ will reduce to a single element and $[p+1, r]$ can shrink down to some $z$ elements where $1 \le z < k$.

Ultimately we can merge this $z + 1$ new elements into one and get the cost for $[l, r]$, which is $g(l, r)$. Formally, we can write:

$g(l, r) = \sum\limits_{i=l}^{r} A_i + \min\limits_p \{~ g(l, p) + \min\limits_z \{~ f(p+1, r, z) ~\} ~\}$

Similary, we can formally define $f(l, r, z)$ as:

$f(l, r, z) = \min\limits_p \{ g(l, p) + f(p + 1, r, z - 1) \}$

We can use prefix-minimum array to store $\min\limits_z \{~ f(l, r, z) ~\}$ as we calculate $f(l, r, z)$.

Thus our overall complexity is $O(n^3k)$ per test case.