Раздел «Алгоритмы».BreakStickProblem:

Задача о распиле палки

Дан отрезок (палка) [0,N], который нужно распилить в помеченых местах L1 , L2, ... , Lk. Числа N, Li — натуральные, 1 <= N <= 1000000, 1 <= k <= 200, 0 < Li < N. Числа Li разные. За один раз мы можем распилить один отрезок на два и заплатить за это цену, равную его длине. Сделайте распилы в помеченых местах, заплатив за это минимальную цену.

Эта задача решается методом динамического программирования. Идея динамического программирования заключается в двух моментах

В нашем случае мы вводим такое параметрическое множество:

Таких задач ( k * (k-1) ) /2. Обозначим a[i][j] ответ на задачу A[i][j], а именно

Нас интересует только элементы матрицы a[i][j] (массива) с j > i.

Понятно, что на диагонали и на второй диагонали матрицы стоят нули. Заполним остальные ячейки массива a "плюс бесконечностью" (в программе это будет просто очень большое число, например N*k + 1).

После этого диагональ за диагональю будем вычислять элементы массива a.

Формат входа

Задание "распилить палку [0, 10] в точках 2,3,4,7" будет на входе описано как
10 4
2 3 4 7
то есть формат входа есть
N k
L1 L2 ... Lk

Формат выхода

Выведите как-нибудь схему распила в первой строчке.

Во второй строчке выведите минимальную цену за распил.

Решение на языке C

Вот код на C, решающий данную задачу:

#include <stdio.h>
#include <sys/types.h>
#define K 202
#define INFTY INT_MAX

int k, n;

/* a[i][j] = цена распила отрезка [L[i], L[j]] */
int a[K][K];

/*    массив координат распилов, упорядоченый по возрастанию   */
int l[K];

/* Печатает  схему разреза отрезка [L[start], L[end]] 
   start и end — номера распилов 
  */
void print_brackets(int start, int end);

int main(int argc, char* argv[])
{
   int i, j, m, k, n;
   scanf("%d%d", &n, &k);

   l[0] = 0;                   /* координата левого конца палки */
   for(i = 1 ; i <= k ; i++)
      scanf("%d", &l[i]);      /* считываем координату i-го распила */
   l[++k] = n;                 /* координата правого конца палки */
   
   /* обнуляем главную (нулевую) и следующую(первую) диагональ*/
   for(i = 0 ; i <= k; i++)
      a[i][i] = a[i][i+1] = 0; 

   for(m = 2; m <= k ; m++)    /* m — номер диагонали  */
      for(i = 0 ; i + m <= k ; i++)
      {
         int L = l[i+m] - l[i];
         a[i][i+m] = INFTY; 
         for(j = 1 ; j < m; j++)
            if( a[i][i+m] > a[i][i+j] + a[i+j][i+m] )
               a[i][i+m] = a[i][i+j] + a[i+j][i+m];
         a[i][i + m] += L;
      }
   
   print_brackets (0, k);
   putc('\n', stdout);
   
   printf("%d\n", a[0][k]);
   system("pause");
   return 0;
}


void
print_brackets(int start, int end)
{
   int L = l[end] - l[start];
   int i, j, m;
   if(end - start <= 1)
   {
      for(i = start ; i < end; i++)
         printf("%d-", l[i]);
      printf("%d", l[end]);
   }
      
   else 
   for(j = 1 ; j  < end - start ; j++  )
      if(a[start][end] == a[start][start+j] + a[start+j][end] + L)
      {
         printf("( ");
         print_brackets(start, start+j ); 
         printf(", ");
         print_brackets(start+j, end ) ;
         printf(" )");
         break;
      }
}

Примеры работы

Вход Выход
10 4
2 3 4 7
( ( 0-2, ( 2-3, 3-4 ) ), ( 4-7, 7-10 ) )
22

Задачи для самостоятельного решения

Нужно перемножить несколько матриц:

Формат входа. Вход

5
2 3 4 5 6 7
означает, что дано 5 матриц, размеры которых равны 2 x 3, 3 x 4, 4 x 5, 5 x 6, 6 x 7. Выведите оптимальную расстановку скобок, обозначая матрицы звездочками. Например
(*((**)(**)))
Запись расстановки скобок должна удовлетворять следующей нотации Google:EBNF+standard
   <скобочная запись> ::= * | (<скобочная запись> <скобочная запись>)

-- ArtemVoroztsov - 23 Mar 2005

AlgorithmClasifyForm
Type: Теория
Scope:  
Strategy: Динамическое программирование
Complexity: Medium