Düzbucaqlı kəsmək#11722

Düzbucaqlı kəsmək (Həll təhlili)

Tutaq ki, $f (a, b)$ f(a, b) — $a \times b$ a \times b ölçülü düzbucaqlını kvadratlara kəsmək üçün lazım olan minimum addım sayıdır. Bu dəyəri $d p [a] [b]$ hüceyrəsində saxlayacağıq.

Əgər düzbucaqlı artıq kvadratdırsa $(a = b)$ (a = b), kəsmələr tələb olunmur, buna görə $f (a, a) = 0$ f(a, a) = 0.

$a \times b$ a \times b ölçülü düzbucaqlı ya şaquli, ya da üfüqi kəsimlə kəsilə bilər. Əvvəlcə şaquli kəsimi nəzərdən keçirək.

Şaquli kəsimdə $a \times b$ a \times b ölçülü düzbucaqlı iki düzbucaqlıya: $a \times k$ a \times k və $a \times (b - k)$ a \times (b - k) bölünür. Alınan düzbucaqlıların deqradasiyaya uğramaması üçün $1 \leq k < b$ 1 \le k < b şərti yerinə yetirilməlidir. Sonra bu düzbucaqlıların hər biri üçün rekursiv olaraq məsələni həll edirik və nəticəyə $1$ əlavə edirik, çünki bir şaquli kəsim etdik. Ən kiçik olan $k$ -ni elə seçirik ki, $f (a, k) + f (a, b - k) + 1$ f(a, k) + f(a, b - k) + 1 cəmi minimal olsun:

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üqi kəsim vəziyyəti üçün oxşar düstur alırıq:

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

Bu iki variant arasında minimal dəyəri seçmək qalır.

Nümunə

Birinci testdə $3$ kəsim tələb olunur:

İlk kəsimlə $3 \times 5$ 3 \times 5 ölçülü düzbucaqlı $3 \times 3$ 3 \times 3 və $2 \times 3$ 2 \times 3 ölçülü düzbucaqlılara bölünür;
İkinci kəsimlə $2 \times 3$ 2 \times 3 ölçülü düzbucaqlı $2 \times 2$ 2 \times 2 və $2 \times 1$ 2 \times 1 ölçülü düzbucaqlılara bölünür;
Üçüncü kəsimlə $2 \times 1$ 2 \times 1 ölçülü düzbucaqlı $1 \times 1$ 1 \times 1 və $1 \times 1$ 1 \times 1 ölçülü düzbucaqlılara bölünür;

Alqoritmin həyata keçirilməsi

Sabitlər və işçi massiv elan edirik.

#define MAX 501
#define INF 0x3F3F3F3F

int dp[MAX][MAX];

$f (a, b)$ f(a, b) funksiyası $a \times b$ a \times b ölçülü düzbucaqlını kvadratlara kəsmək üçün lazım olan minimum addım sayını qaytarır.

int f(int a, int b)
{

Əgər düzbucaqlı artıq kvadratdırsa $(a = b)$ (a = b), kəsmələr tələb olunmur.

  if (a == b) return 0;

Əgər $f (a, b)$ f(a, b) dəyəri hələ hesablanmayıbsa $(d p [a] [b] = \infty)$ (dp[a][b] = ∞), onu hesablayırıq.

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

Bütün mümkün şaquli kəsimləri həyata keçiririk.

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

Bütün mümkün üfüqi kəsimləri həyata keçiririk.

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

Nəticəni $f (a, b) = d p [a] [b]$ f(a, b) = dp[a][b] olaraq qaytarırıq.

  return dp[a][b];
}

Proqramın əsas hissəsi. Düzbucaqlının $a$ və $b$ ölçülərini oxuyuruq.

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

Cavabı hesablayırıq və çap edirik.

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