Розрізання прямокутника#11722

Розрізання прямокутника (Розбір)

Нехай $f (a, b)$ f(a, b) — найменша кількість ходів, за яке прямокутник розміром $a \times b$ a \times b можна розрізати на квадрати. Будемо зберігати це значення в осередку $d p [a] [b]$ .

Якщо прямокутник вже є квадратом $(a = b)$ (a = b), розрізи не потрібні, тому $f (a, a) = 0$ f(a, a) = 0.

Прямокутник $a \times b$ a \times b можна розрізати або вертикальним, або горизонтальним розрізом. Розглянемо спочатку вертикальний розріз.

При вертикальному розрізі прямокутник $a \times b$ a \times b ділиться на два прямокутники: $a \times k$ a \times k і $a \times (b - k)$ a \times (b - k). Щоб отримані прямокутники були невиродженими, повинна виконуватися умова $1 \leq k < b$ 1 \le k < b. Потім рекурсивно розв'язуємо задачу для кожного з цих двох прямокутників і додаємо $1$ до результату, оскільки ми зробили один вертикальний розріз. При цьому обираємо таке $k$ , для якого сума $f (a, k) + f (a, b - k) + 1$ f(a, k) + f(a, b - k) + 1 найменша:

f (a, b) = 1 \leq k < b min (f (a, k) + f (a, b - k)) + 1

f(a, b) = \min_{\substack{1 \le k < b}} (f(a, k) + f(a, b - k)) + 1

Для випадку горизонтального розрізу отримуємо аналогічну формулу:

f (a, b) = 1 \leq k < a min (f (k, b) + f (a - k, b) + 1

f(a, b) = \min_{\substack{1 \le k < a}} (f(k, b) + f(a - k, b) + 1

Залишається вибрати мінімальне значення серед цих двох варіантів.

Приклад

У першому тесті потрібно виконати $3$ розрізи:

Першим розрізом прямокутник $3 \times 5$ 3 \times 5 розділяється на $3 \times 3$ 3 \times 3 і $2 \times 3$ 2 \times 3;
Другим розрізом прямокутник $2 \times 3$ 2 \times 3 розділяється на $2 \times 2$ 2 \times 2 і $2 \times 1$ 2 \times 1;
Третім розрізом прямокутник $2 \times 1$ 2 \times 1 розділяється на $1 \times 1$ 1 \times 1 і $1 \times 1$ 1 \times 1;

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

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

#define MAX 501
#define INF 0x3F3F3F3F

int dp[MAX][MAX];

Функція $f (a, b)$ f(a, b) повертає найменшу кількість ходів, за яке прямокутник розміром $a \times b$ a \times b можна розрізати на квадрати.

int f(int a, int b)
{

Якщо прямокутник вже є квадратом $(a = b)$ (a = b), розрізи не потрібні.

  if (a == b) return 0;

Якщо значення $f (a, b)$ f(a, b) ще не обчислено $(d p [a] [b] = \infty)$ (dp[a][b] = ∞), то обчислюємо його.

  if (dp[a][b] == INF)
  {

Виконуємо всі можливі вертикальні розрізи.

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

Виконуємо всі можливі горизонтальні розрізи.

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

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

  return dp[a][b];
}

Основна частина програми. Читаємо розміри прямокутника $a$ і $b$ .

scanf("%d %d", &a, &b);

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

memset(dp, 0x3F, sizeof(dp));
printf("%d\n", f(a, b));