| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Динамическое программирование |
| Автор: n1k0LaY 18.6.2008, 11:43 |
| вообщем простая олимп школьная задачка)) что то не могу реализовать эффективное решение( не проходит по всем тестам) не буду копи-пастить Ссылка http://acm.dvpion.ru/?main=task&id_task=29 Собственно не прошу решить, а обьяснить Я понимаю что нужно создать 4 переменных, и считывать в них пошагово, и выбирать либо прыгнуть на 3 либо на 1, но вот что то не проходит, прав ли я?) Да и не пойму как сделать эффектиную проверку (на сколько прыгнуть). |
| Автор: 2p0i 20.6.2008, 11:29 |
| Храним в каждый момент времени высоты двух последних платформ (y1 и y2) и оптимальное количество энергии, нужное, чтобы до них добраться (x1 и x2). Считываем высоту следующей платформы: y. Тогда оптимальная энергия для новой платформы будет x = min(x2+abs(y-y2), x1+3*abs(y-y1)). Меняем переменные после очередного шага: x1 := x2, x2 := x; y1 := y2; y2 := y. |
| Автор: fukusu 29.1.2010, 20:29 | ||
А что будешь делать если на вход пойдет: 4 1 5 2 5 по твоей логике сначала будет прыжок с 1 на 2, а потом на 5, что в итоге даст 3+3 ед. потраченной энергии, хотя оптимальным будет сначала с 1 на 5, а потом через платформу на 5, что в итоге даст 4 ед. затраченной энергии |
| Автор: Akina 29.1.2010, 21:31 |
| Храним в каждый момент времени минимум стоимости прыжка на две последние платформы. Просчитываем стоимость прыжка на следующую с каждой из них, оставляем минимум из двух. Всё собсно. Скажем применительно к N 1 5 2 5 ... Шаг 1 платформа 1, стоимость 0 платформа 2, стоимость 5-1=4 Шаг 2 платформа 3, прыжок с платформы 1, стоимость 0+3*(2-1)=3 платформа 3, прыжок с платформы 2, стоимость 4+(5-2)=7 минимальное 3 оставляем: платформа 2, стоимость 4 платформа 3, стоимость 3 Шаг 3 платформа 4, прыжок с платформы 2, стоимость 4+3*(5-5)=4 платформа 4, прыжок с платформы 3, стоимость 3+(5-2)=6 минимальное 4 оставляем: платформа 3, стоимость 3 платформа 4, стоимость 4 ... |