Дистанционная подготовка: Разбор.
Разбор.
от Никита Пушкин - Пятница 23 Май 2014, 21:51
210. Гвоздики
  Что такое m и k-m в этом разборе?
Re: Разбор.
от Григорий Резников - Суббота 24 Май 2014, 19:28
  k - это некий указатель, которым мы пробегаем от 1 до N.
А k-m - это просто сокращение от "катым")
Re: Разбор.
от Никита Пушкин - Суббота 24 Май 2014, 20:30
  "Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним (k-м) и предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-м) и предпредпоследним ((k-2)-м) она может либо быть, либо не быть."

А почему это оптимальная конфигурация?

И еще, я что-то не понимаю примера. Как можно ниточкой длиной 6 повязать все эти гвоздики? Что с чем надо связать? Буду очень признателен за помощь.
Re: Разбор.
от Никита Пушкин - Суббота 24 Май 2014, 20:45
  Написал кое-какую программу, но она почему-то не проходит даже теста в условии(которого я все равно не могу понять). Подскажите, что не так?
Re: Разбор.
от Григорий Резников - Суббота 24 Май 2014, 20:52
  Про пример:
1)Соединим гвоздики 0 и 2 (длина нитки - 2)
2) соединим гвоздики 2 и 4 (длина нитки - 2)
3) Соединим гвоздики 10 и 12 (длина нитки - 2)
В итоги 3 нитки по 2, то есть 6;
Фишка в том, что необязательно, чтобы по нитке можно было пройти между каждой парой гвоздей, а в том, чтобы у каждого гвоздя была нитка.

Теперь про разбор:
Мы хотим потратить минимальное количество нитки. Когда мы "подключаем" последний гвоздик, самый дешевый вариант- привязать его к предпоследнему. Предпоследний уже привязан, поэтому его пропускаем. Теперь предпредпоследний(k-2): для него уже есть 2 варианта: привязать его к k-3 и к k-1, из которых выберем самый выгодный.
Поэтому в формуле ak=min(ak-1,ak-2)+lk-1 то, что в функции min отвечает за выбор лучшего варианта для k-2 гвоздика,а lk-1-добавляет расстояние между последним и предпоследним.
Я как-то коряво объяснил, так что спрашивайте, если что.
Re: Разбор.
от Никита Пушкин - Суббота 24 Май 2014, 21:18
  "Предпоследний уже привязан, поэтому его пропускаем."

А почему его пропускаем, если это самый выгодный вариант?

У меня вот такой ряд расстояний по тестам из примера получается:
0, 2, 2, 8, 4.
Что не так? Формула точно такая же, как и у Вас.
Re: Разбор.
от Никита Пушкин - Суббота 24 Май 2014, 21:45
  Хорошо, давайте возьмем такой вариант: 0 2 4.
По формуле получается 2(первый элемент 0, второй 2, третий 2). А по уму должно быть 4.