Cutting a stick#11261

Cutting a stick (Editorial)

Let the array $m$ contain the cutting points: $m_{1}, ..., m_{n}$ m_1, ..., m_n. Add the start and end points: $m_{0} = 0$ m_0 = 0 and $m_{n + 1} = l$ m_{n+1} = l.

Let the function $f (a, b)$ f(a, b) return the minimal cost of cutting a stick from $m_{a}$ m_a to $m_{b}$ m_b considering the necessary cutting points within the segment. There are no cutting points within the segment $[m_{a}; m_{a + 1}]$ [m_a; m_{a + 1}], so $f (a, a + 1) = 0$ f(a, a + 1) = 0. The solution to the problem will be the value of $f (0, n + 1)$ f(0, n + 1). Store the computed values of $f (a, b)$ f(a, b) in the cells of the array $d p [a] [b]$ .

Let the segment of the stick $[m_{a}, m_{b}]$ [m_a, m_b] be cut into several pieces. If the first cut is made at point $m_{i} (a < i < b)$ m_i~(a < i < b), the cost of the cut itself will be $m_{b} - m_{a}$ m_b - m_a. Then, the remaining pieces need to be cut at the costs $f (a, i)$ f(a, i) and $f (i, b)$ f(i, b), respectively. Choose $i$ to minimize the total cost:

f (a, b) = a < i < b min (f (a, i) + f (i, b)) + m_{b} - m_{a}

f(a, b) = \min_{\substack{a<i<b}}(f(a,i) + f(i,b)) + m_b - m_a

Example

Consider the second test case. Here is one possible way to cut a stick of length $10$ with a cost of $10 + 7 + 3 + 3 = 23$ 10 + 7 + 3 + 3 = 23:

Now, consider the optimal way to cut the stick, which has a cost of $10 + 6 + 3 + 3 = 22$ 10 + 6 + 3 + 3 = 22:

Algorithm implementation

Declare constants and arrays.

#define MAX 55
#define INF 0x3F3F3F3F
int dp[MAX][MAX];
int m[MAX];

The function $f (a, b)$ f(a, b) returns the minimum cost of cutting a piece of stick on the segment $[a; b]$ at the cutting points located inside the segment.

int f(int a, int b)
{

If $a + 1 = b$ a + 1 = b, then there are no cutting points within the segment $[a; b]$ . Return $0$ .

  if (b - a == 1) return 0;

If the value of $f (a, b)$ f(a, b) is already computed, return it.

  if (dp[a][b] != INF) return dp[a][b];

Make a cut at the point $i (a < i < b)$ i~(a < i < b). Compute the cost as follows:

f (a, b) = a < i < b min (f (a, i) + f (i, b)) + m_{b} - m_{a}

f(a, b) = \min_{\substack{a<i<b}}(f(a,i) + f(i,b)) + m_b - m_a

  for (int i = a + 1; i < b; i++)
    dp[a][b] = min(dp[a][b], m[b] - m[a] + f(a, i) + f(i, b));

Return the result $f (a, b) = d p [a] [b]$ f(a, b) = dp[a][b].

  return dp[a][b];
}

The main part of the program. Read the input data for each test case.

while(scanf("%d",&l),l)
{
  scanf("%d",&n);

Add the start and end cutting points: $m_{0} = 0, m_{n + 1} = l$ m_0 = 0, m_{n+1} = l.

  m[0] = 0; m[n+1] = l;
  for(i = 1; i <= n; i++)
    scanf("%d",&m[i]);

Initialize the $d p$ array.

  memset(dp,0x3F,sizeof(dp));

Find and print the answer.

  printf("The minimum cutting is %d.\n",f(0,n+1));
}