Розрізання палки#11261

Розрізання палки (Розбір)

Нехай масив $m$ містить точки розпилу: $m_{1}, ..., m_{n}$ m_1, ..., m_n. Додамо початкову і кінцеву точки: $m_{0} = 0, m_{n + 1} = l$ m_0 = 0, m_{n+1} = l.

Нехай функція $f (a, b)$ f(a, b) повертає мінімальну вартість розпилу відрізку палиці від $m_{a}$ m_a до $m_{b}$ m_b з урахуванням необхідних точок розпилу, що знаходяться всередині відрізка. Усередині відрізка $[m_{a}; m_{a + 1}]$ [m_a; m_{a + 1}] точок розпилу немає, тому $f (a, a + 1) = 0$ f(a, a + 1) = 0. Відповіддю на задачу буде значення $f (0, n + 1)$ f(0, n + 1). Розраховані значення $f (a, b)$ f(a, b) зберігаємо в осередках масиву $d p [a] [b]$ .

Нехай відрізок палиці $[m_{a}, m_{b}]$ [m_a, m_b] слід розпиляти на кілька частин. Якщо перший розпил ми здійснимо в точці $m_{i} (a < i < b)$ m_i~(a < i < b), то вартість самого розпилу складе $m_{b} - m_{a}$ m_b - m_a. Далі слід розпиляти залишені шматки відповідно за ціною $f (a, i)$ f(a, i) і $f (i, b)$ f(i, b). Значення $i$ слід вибрати так, щоб мінімізувати загальну вартість:

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

Приклад

Розглянемо другий тест. Наведемо один з можливих методів розпилу палиці довжини $10$ вартістю $10 + 7 + 3 + 3 = 23$ 10 + 7 + 3 + 3 = 23:

Розглянемо оптимальний метод розпилу вартістю $10 + 6 + 3 + 3 = 22$ 10 + 6 + 3 + 3 = 22:

Реалізація алгоритму

Оголосимо константи та робочі масиви.

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

Функція $f (a, b)$ f(a, b) повертає мінімальну вартість розрізу шматка палиці на відрізку $[a; b]$ з урахуванням точок розпилу, що знаходяться всередині цього відрізка.

int f(int a, int b)
{

Якщо $a + 1 = b$ a + 1 = b, то всередині відрізка $[a; b]$ точок розрізу немає. Повертаємо $0$ .

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

Якщо значення $f (a, b)$ f(a, b) вже обчислено, то повертаємо його.

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

Здійснюємо розріз у точці $i (a < i < b)$ i~(a < i < b). Обчислюємо вартість наступним чином:

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));

Повертаємо результат $f (a, b) = d p [a] [b]$ f(a, b) = dp[a][b].

  return dp[a][b];
}

Основна частина програми. Читаємо вхідні дані для кожного тесту.

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

Додамо початкову і кінцеву точки розпилу: $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]);

Ініціалізуємо масив $d p$ .

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

Обчислюємо і виводимо відповідь.

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