Объединение блоков

Для решения данной задачи можно применять как восходящее, так и нисходящее динамическое программирование. Рассмотрим второй вариант решения. Определим двумерный массив a для хранения промежуточных вычислений, где в a[l][r] будет храниться минимальное число технологических операций, необходимых для объединения блоков с номерами с l по r. Первоначально определим значения a[x][x]=0 (последовательность из одного блока не требует операций) и a[i][j]=-1 при i<>j (полагаем, что пока эти значения не известны).

Далее, реализуем рекурсивную функцию g(l,r), которая будет вычислять минимальное число технологических операций для последовательности блоков с l-го по r-й. После вычисления такого значения будем помещать результат в a[l][r]. Это позволит избежать повторных вычислений одних и тех же значений: при вызове функции мы будем возвращать значение a[l][r], если оно определено, в противном случае будем проводить вычисления. Предположим, что существует оптимальное объединение блоков на отрезке [l,r], где l < r. Тогда последнее объединение блоков произойдет между некоторыми блоками t и t+1, где t принадлежит отрезку [l, r-1]. В результате чего оптимальный результат g(l,r) будет равен g(l,t)+g(t+1,r)+m[l]*k[r], где m и k - соответствующие массивы с технологическими параметрами. Для определения значения t нужно перебрать все возможные такие значения и найти наименьшее. В силу того, что вызов функции g внутри себя приводит к сближению границ, то всегда можно гарантировать выход из рекурсии в силу определенности a[x][x]. Ответом на задачу будет служить значение функции g(1,n).

Приведем алгоритмическую реализацию данного механизма:

  int m[100],k[100],a[100][100]

  int g(l, r){
    if(a[l][r]<0){
      mi=inf;
      for t=l..r-1
        mi=min(mi,g(l,t)+g(t+1,r))
      a[l][r]=mi+m[l]*k[r]
    }
    return a[l][r]
  }

  read(n)
  for i=1..n read(m[i],k[i])

  for i=1..n
    for j=1..n
      if(i=j) a[i][j]=0 else a[i][j]=-1

  write(g(1,n))

[Обсуждение] [Все попытки] [Задача]