суббота, 30 января 2010 г.

Задача “Цветочный магазин” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея: Данная задача была представлена на IOI’99. Разбор этой задачи можно найти в первой книги Михаила Долинского и в  “Методике решения задач по информатике”. Рекомендую ознакомится.
Пусть f(i,j) – максимальная эстетическая ценность размещения i букетов по j вазам.
Рассмотри первоначальная таблицу a:

 

1-ая ваза

2-ая ваза

3-я ваза

4-я ваза

5-я ваза

1 (азалии)

7

23

-5

-24

16

2 (бегонии)

5

21

-4

10

23

3 (гвоздики)

-21

5

-4

-20

20

Шаг 0. f[0][0] = a[0][0].
Шаг 1. Заполним результирующую матрицу f  для i=1:

7 23 23 23 23
* * * * *
* * * * *

На текущем шаге у нас есть один букет и количество ваз, варьирующихся от 1 до 5. Если мы имеет в наличии i ваз и один букет, то логично, что для получения максимальной эстетичности нужно выбрать самую эстетичную вазу с первой по i-ую.
Шаг 2. Т.к. бегонии могут находится только за азалиями, то элемент f[1][0] будет непределен, а значение f[1][1] можно определить однозначно, т.к. имея в наличии 2 букета и 2 вазы существует только один способ расставить их. Следовательно f[1][1] = f[0][0] + a[1][1]. Аналогично действуем в случае, когда имеем 3 букета и 3 вазы.

7 23 23 23 23
* 28 * * *
* * 24 * *

Шаг 3. Для заполнения оставшейся таблицы используем следующий принцип. Для нахождения f[i][j] мы можем поставить i-ый букет в j-ую вазу. При этом эстетичность  будет равна a[i][j] + f[i-1][j-1]. Но при этом нас никто этого делать не заставляет. Возможно предыдущее размещение f[i][j-1] дает лучшую эстетическую характеристику. Поэтому на этом шаге мы должны выбрать максимальное из двух предложенных значений:
f[i][j] = max(a[i][j] + f[i-1][j-1],f[i][j-1]).
Шаг 3 стоит повторять до полного заполнения результирующей матрицы f. Очевидно, что ответ будет находится в нижней правой ячейке.

7 23 23 23 23
* 28 28 33 46
* * 24 24 53

Остался еще один неоговоренный момент: “Как будет восстанавливать номера ваз, в которых будут находится букеты.” Этот вопрос вынесем на самостоятельное рассмотрение.
Исходный код: здесь

3 комментария:

  1. красиво за n*n, я делал за pow(n,3) особо не заморачиваясь, но допустил досадную ошибку и ломал голову полтора часа рабочего времени сегодня :(

    ОтветитьУдалить
  2. Хорошая работа - это такая работа, где есть возможность порешать таски в рабочее время.
    Лучшая работа - это такая работа, где порешивание тасков и является твоей работой!

    ОтветитьУдалить