Redaksiya

Let $f(i,j)$ represent the minimum cost to reduce the subarray $[a_i,...,a_j]$ to a single element. This value will be stored in the cell $dp[i][j]$.

Obviously, $f(i,i)=0$.

From the problem statement, it follows that

Now, let’s compute $f(i,i+2)$. Reducing three numbers into one can be done in two ways:

• Merge $a_i$ and $a_{i+1}$ with a cost of $k\cdot (a_i+a_{i+1})$, then merge $a_i+a_{i+1}$ and $a_{i+2}$ at a cost of $k\cdot (a_i+a_{i+1}+a_{i+2})$.

  

• Merge $a_{i+1}$ and $a_{i+2}$ with a cost of $k\cdot (a_{i+1}+a_{i+2})$, then merge $a+i$ and $a_{i+1}+a_{i+2}$ at a cost of $k\cdot (a_i+a_{i+1}+a_{i+2})$.

  

Thus

Now, let’s consider calculating the value of $f(i,j)$. To reduce the subarray $[a_i,...,a_j]$ to a single element equal to $a_i+...+a_j$, we need to choose some value $p(i\le p<j)$. Then, recursively solve the problem for the subarrays $[a_i,...,a_p]$ and $[a_{p+1},...,a_j]$, and finally merge the elements $a_i+...+a_p$ and $a_{p+1}+...+a_j$. The value of $p$ should be chosen in such a way that the total transformation cost is minimized:

For efficient computation of sums $a_i+...+a_j$ use a prefix sum array $pref$, where

so that $a_i+...+a_j=pref[j]-pref[i-1]$.

Algorithm implementation

Let’s declare constants and arrays.

#define MAX 101
#define INF 0x3F3F3F3F
int dp[MAX][MAX], a[MAX], pref[MAX];

The function $f(i,j)$ returns the minimum cost to transform the subarray $[a_i,...,a_j]$ into a single element.

int f(int i, int j)
{
  if (dp[i][j] == INF)
    for (int p = i; p < j; p++)
      dp[i][j] = min(dp[i][j], f(i, p) + f(p + 1, j) + (pref[j] - pref[i - 1]) * k);
    return dp[i][j];
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &k);
memset(dp, 0x3F, sizeof(dp));
for (i = 1; i <= n; i++)
{
  scanf("%d", &a[i]);
  dp[i][i] = 0;

Compute the array of prefix sums.

  pref[i] = pref[i - 1] + a[i];
}

Compute and print the answer.

printf("%d\n", f(1, n));

Python implementation

Let’s declare the constant for infinity.

INF = float('inf')

The function $f(i,j)$ returns the minimum cost to transform the subarray $[a_i,...,a_j]$ into a single element.

def f(i, j):
  if dp[i][j] == INF:
    for p in range(i, j):
      dp[i][j] = min(dp[i][j], f(i, p) + f(p + 1, j) + (pref[j] - pref[i - 1]) * k)
  return dp[i][j]

The main part of the program. Read the input data.

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))

Compute the array of prefix sums.

pref = [0] * (n + 1)
for i in range(1, n + 1):
  pref[i] = pref[i - 1] + a[i]

Initialize the $dp$ array.

dp = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
  dp[i][i] = 0

Compute and print the answer.

print(f(1, n))