Зменшити масив#11719

Зменшити масив (Розбір)

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

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

From the problem statement, it follows that

f (i, i + 1) = k \cdot (a_{i} + a_{i + 1})

f(i, i + 1) = k \cdot (a_i + a_{i+1})

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

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

Thus

f (i, i + 2) = min (k \cdot (a_{i} + a_{i + 1}) + k \cdot (a_{i} + a_{i + 1} + a_{i + 2}), k \cdot (a_{i + 1} + a_{i + 2}) + k \cdot (a_{i} + a_{i + 1} + a_{i + 2}))

f(i, i + 2) = min(k \cdot (a_i + a_{i+1}) + k \cdot (a_i + a_{i+1} + a_{i+2}), k \cdot (a_{i+1} + a_{i+2}) + k \cdot (a_i + a_{i+1} + a_{i+2}))

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

f (i, j) = i \leq p < j min (f (i, p) + f (p + 1, j)) + k \cdot (a_{i} + ... + a_{j})

f(i, j) = \min_{i \le p < j} (f(i,p) + f(p + 1, j)) + k \cdot (a_i + ... + a_j)

For efficient computation of sums $a_{i} + ... + a_{j}$ a_i + ... + a_j use a prefix sum array $p r e f$ , where

p r e f [i] = a_{1} + ... + a_{i},

pref[i] = a_1 + ... + a_i,

so that $a_{i} + ... + a_{j} = p r e f [j] - p r e f [i - 1]$ 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)$ f(i, j) returns the minimum cost to transform the subarray $[a_{i}, ..., a_{j}]$ [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];
}

C++

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)$ f(i, j) returns the minimum cost to transform the subarray $[a_{i}, ..., a_{j}]$ [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 $d p$ 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))