Гвоздики

@VinnyPyxxer · Регистрация: 17.10.2017

Студворк — интернет-сервис помощи студентам

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Входные данные
В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек.

@hacthies · 03.10.2019, 19:36

Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу:
найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек ak).

Можно считать, что любая ниточка связывает два соседних гвоздика
(иначе ее можно разрезать на несколько частей, связывающих все гвоздики между теми, которые связывала наша ниточка изначально).

Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним
(k-м) и предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-м)
и предпредпоследним ((k-2)-м) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков
удовлетворяют условию задачи, во втором - первые k-2. Значит ak=min(ak-1,ak-2)+lk-1,k, где lk-1,k - расстояние между k-м и k-1-м гвоздиками (в отсортированном массиве).
Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно
(в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000).
Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе aN.

Число действий, выполненных данным алгоритмом, пропорционально N.

Копировал с информатикса. Достаточно криво написано, но вроде бы понятно

@iSmokeJC · 04.10.2019, 08:59

Не по теме:

hacthies, знаешь, что сейчас думает ТС? Как в анекдоте -
Всплыли 2 подлодки:
- не подскажете, где Америка?
- зюйд-зюйд-вест
- ты не умничай, ты рукой покажи

@hacthies · 04.10.2019, 16:30

Ну вообще, да.
Ок. VinnyPyxxer, это задача на динамическое программирование, если ты вдруг этого не понимаешь. Я тебе написал алгоритм, где сама формула dp[i] прописана. Делай, если не получается, пиши.

@Shuka · 10.07.2023, 02:57

Python
1
2
3
4
5
6
7
8
9
10
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
d = [0] * n
d[1] = lst[1] - lst[0]
if n > 2:
    d[2] = lst[2] - lst[0]
    for i in range(3, n):
        d[i] = min(d[i - 2], d[i - 1]) + lst[i] - lst[i - 1]
print(d[n - 1])

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@VinnyPyxxer 1 / 1 / 0 Регистрация: 17.10.2017 Сообщений: 51

	Гвоздики 03.10.2019, 11:52. Показов 7917. Ответов 4 Метки нет (Все метки) На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна. Входные данные В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000). Выходные данные В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек. 0

@hacthies 8 / 12 / 2 Регистрация: 08.08.2019 Сообщений: 63
	03.10.2019, 19:36
	Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек ak). Можно считать, что любая ниточка связывает два соседних гвоздика (иначе ее можно разрезать на несколько частей, связывающих все гвоздики между теми, которые связывала наша ниточка изначально). Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним (k-м) и предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-м) и предпредпоследним ((k-2)-м) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков удовлетворяют условию задачи, во втором - первые k-2. Значит ak=min(ak-1,ak-2)+lk-1,k, где lk-1,k - расстояние между k-м и k-1-м гвоздиками (в отсортированном массиве). Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно (в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000). Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе aN. Число действий, выполненных данным алгоритмом, пропорционально N. Копировал с информатикса. Достаточно криво написано, но вроде бы понятно 0

@iSmokeJC
	04.10.2019, 08:59
	Не по теме: hacthies, знаешь, что сейчас думает ТС? Как в анекдоте - Всплыли 2 подлодки: - не подскажете, где Америка? - зюйд-зюйд-вест - ты не умничай, ты рукой покажи 0

@hacthies 8 / 12 / 2 Регистрация: 08.08.2019 Сообщений: 63
	04.10.2019, 16:30
	Ну вообще, да. Ок. VinnyPyxxer, это задача на динамическое программирование, если ты вдруг этого не понимаешь. Я тебе написал алгоритм, где сама формула dp[i] прописана. Делай, если не получается, пиши. 0