Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
miraina
0 / 0 / 0
Регистрация: 22.05.2013
Сообщений: 5
1

Интересная задачка на динамическое программирование

22.05.2013, 17:25. Просмотров 588. Ответов 2
Метки нет (Все метки)

Столкнулась со следующей задачей:

В спортивном параде должны были идти две колонны спортсменов с флагами, но когда колонны уже выстроились перед выходом, оказалось, что ширины дорожки для двух колонн не хватит. Экстренно было принято решение совместить две колонны в одну. Сначала хотели пустить вперед первую колонну, а следом за ней вторую, но, посовещавшись, чтобы никого не обидеть, решили перемешать две колонны. При этом, чтобы улучшить эстетическую составляющую зрелища, чередование участников колонн должно было происходить так, чтобы сумма разностей высот соседних флагов была минимальна.

Зная высоты флагов и их очередность в каждой колонне по отдельности, определите какую минимальную сумму разностей высот соседних флагов могут получить организаторы шествия, объединив колонны, но не меняя порядок выхода участников каждой из них.

Ввод
3 3
1 5 3
2 2 6
Вывод
8

Перебор обычный - естественно не проходит. Решила, что это все-таки динамика. Всегда меня учили, что для динамики нужно выбрать базу и шаг, по которому идем. Помогите советом - как сделать оптимальнее и правильнее?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2013, 17:25
Ответы с готовыми решениями:

Динамическое программирование
гайс, помогите пожалуйста есть одномерный массив длинной N мы можем ходить по...

Динамическое программирование
Приветствую, форумчане. Так уж вышло, что жизнь свела меня с динамическим...

Динамическое программирование
Добрый вечер. Мне задали написать задачи на динамическое программирование, но...

Динамическое программирование
Есть задача: Необходимо подсчитать кол-во вариантов и вывести их для сдачи для...

Динамическое программирование - задача
Добрый вечер! На днях попалась такая задача: Миша записывает 2 числа: n и m,...

2
salam
181 / 162 / 29
Регистрация: 10.07.2012
Сообщений: 774
23.05.2013, 16:00 2
ограничения укажите, пожалуйста.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
23.05.2013, 17:49 3
Интересная задачка, подпишусь на тему, послушаю. Вероятно здесь нужна теория. Если без нее, "сходу", то примерно так

- каким-то образом (да хоть случайным) расставляем "пары"
- берем наихудшую пару и пытаемся ее улучшить выбирая новых партнеров. При этом образуются "свободные электроны" которым опять надо найти пары. В общем получается "волна" которая должна затухнуть

Начсет ограничений (предыдущий пост) не понял. По-моему все уже определено
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2013, 17:49

Лесенка - динамическое программирование
Здраствуйте. У меня есть одна классическая задачка про Лесенку. Лесенка ...

задача динамическое программирование
В город N приехал цирк с комндой атлетов. Они хотят удивить горожан города N --...

Динамическое программирование. Кааак?
Здравствуйте. Подскажите пожалуйста, в каком направлении двигаться для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru