Задача на динамическое программирование

@smalyarovsky · Регистрация: 12.03.2019

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

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

Входные данные
В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 < = N < = 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек.

Очень прошу помочь!

@Gdez · 05.11.2020, 19:46

smalyarovsky, Так вроде = максимум(координаты) - минимум(координаты) ?

@smalyarovsky · 05.11.2020, 20:05 **[ТС]**

Не понимаю, что вы имеете в виду

@Gdez · 05.11.2020, 20:18

smalyarovsky, координаты на одной числовой оси или на плоскости (х,у)?

@smalyarovsky · 05.11.2020, 20:23 **[ТС]**

Только по оси x, дается только одно число. Неправ, надо было добавить тесты. Сейчас добавлю

@eaa · 05.11.2020, 20:30

smalyarovsky,
числа отсортируйте для начала.

@smalyarovsky · 05.11.2020, 22:17 **[ТС]**

А остальной алгоритм?

@Miryz · 05.11.2020, 23:53

smalyarovsky,

Python
1
2
3
4
5
6
7
N = int(input())
lst = sorted(list(map(int, input().split())))
a = [0] * (N+1)
a[1] = 10**5
for k in range(2, N+1):
    a[k] = min(a[k - 1], a[k - 2]) + lst[k-1] - lst[k-2]
print(a[N])

Надеюсь ввод/вывод через файлы сам напишешь...

@smalyarovsky · 06.11.2020, 09:17 **[ТС]**

Зашло, спасибо!

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36

	Задача на динамическое программирование 05.11.2020, 19:27. Показов 12125. Ответов 8 Метки динамическое программирование, с++ (Все метки) На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна. Входные данные В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 < = N < = 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000). Выходные данные В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек. Очень прошу помочь! 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.11.2020, 19:46
	smalyarovsky, Так вроде = максимум(координаты) - минимум(координаты) ? 0

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	05.11.2020, 20:05 [ТС]
	Не понимаю, что вы имеете в виду 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.11.2020, 20:18
	smalyarovsky, координаты на одной числовой оси или на плоскости (х,у)? 0

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	05.11.2020, 20:23 [ТС]
	Только по оси x, дается только одно число. Неправ, надо было добавить тесты. Сейчас добавлю 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	05.11.2020, 20:30
	smalyarovsky, числа отсортируйте для начала. 0

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	05.11.2020, 22:17 [ТС]
	А остальной алгоритм? 0

@smalyarovsky 0 / 0 / 0 Регистрация: 12.03.2019 Сообщений: 36
	06.11.2020, 09:17 [ТС]
	Зашло, спасибо! 0

Задача на динамическое программирование

Решение