Əsanın kəsilməsi#11261

Əsanın kəsilməsi (Həll təhlili)

Tutaq ki, $m$ massivində kəsilmə nöqtələri var: $m_{1}, ..., m_{n}$ m_1, ..., m_n. Başlanğıc və son nöqtələri əlavə edək: $m_{0} = 0, m_{n + 1} = l$ m_0 = 0, m_{n+1} = l.

Tutaq ki, $f (a, b)$ f(a, b) funksiyası $m_{a}$ m_a-dan $m_{b}$ m_b-ya qədər olan çubuq parçasını minimum kəsilmə xərci ilə verir ki, daxilindəki zəruri kəsilmə nöqtələrini də nəzərə alaq. $[m_{a}; m_{a + 1}]$ [m_a; m_{a + 1}] intervallı daxilində kəsilmə nöqtəsi yoxdur, buna görə $f (a, a + 1) = 0$ f(a, a + 1) = 0. Məsələnin cavabı $f (0, n + 1)$ f(0, n + 1) olacaq. Hesablanmış $f (a, b)$ f(a, b) dəyərlərini $d p [a] [b]$ massivinin hücrələrində saxlayırıq.

Tutaq ki, çubuq parçası $[m_{a}, m_{b}]$ [m_a, m_b] bir neçə hissəyə kəsilməlidir. İlk kəsimi $m_{i} (a < i < b)$ m_i~(a < i < b) nöqtəsində edəriksə, kəsimin xərci $m_{b} - m_{a}$ m_b - m_a təşkil edəcək. Sonra qalan parçaları müvafiq olaraq $f (a, i)$ f(a, i) və $f (i, b)$ f(i, b) xərci ilə kəsmək lazımdır. $i$ dəyərini ümumi xərci minimallaşdırmaq üçün seçmək lazımdır:

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

Nümunə

İkinci testə baxaq. Çubuq uzunluğu $10$ olan bir kəsim metodunu $10 + 7 + 3 + 3 = 23$ 10 + 7 + 3 + 3 = 23 xərci ilə göstərək:

Optimal kəsim metodunu $10 + 6 + 3 + 3 = 22$ 10 + 6 + 3 + 3 = 22 xərci ilə nəzərdən keçirək:

Alqoritmin icrası

Sabitləri və işçi massivlərini elan edək.

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

$f (a, b)$ f(a, b) funksiyası, daxilindəki kəsim nöqtələrini nəzərə alaraq $[a; b]$ intervalında çubuq parçasının kəsilməsinin minimum xərci qaytarır.

int f(int a, int b)
{

Əgər $a + 1 = b$ a + 1 = b olarsa, $[a; b]$ intervalında kəsim nöqtəsi yoxdur. $0$ qaytarırıq.

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

Əgər $f (a, b)$ f(a, b) dəyəri artıq hesablanmışsa, onu qaytarırıq.

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

$i (a < i < b)$ i~(a < i < b) nöqtəsində kəsim edirik. Xərci aşağıdakı kimi hesablayırıq:

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

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. Hər test üçün giriş məlumatlarını oxuyuruq.

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

Başlanğıc və son kəsim nöqtələrini əlavə edək: $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]);

Məxəzini $d p$ massivini alqı-initiatiaiz edək.

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

Cavabı hesablayıb çap edirik.

  printf("Minimum kəsim %d.\n",f(0,n+1));
}