Задача на динамику

@MihaniX · Регистрация: 06.08.2013

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

Помогите решить задачу на динамическое программирование.

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

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

Формат выходных данных
Выведите единственное число — минимальную суммарную длину всех ниточек.

Задали на кружке, решить не получается

@MihaniX · 06.04.2014, 17:04 **[ТС]**

апп

@gng · 07.04.2014, 21:41

Оптимизация нулевая, но считает, вроде, правильно. Проверьте.
На входе предполагается упорядоченный набор координат

Python
1
2
3
4
5
6
7
8
9
def maxl (i):
    if i > n-3:
        return 0
    return x[i+1] - x[i] + max (maxl (i+2), maxl (i+3));
 
n= input()
x= input()
m= max( maxl(1),maxl (2))
print x[-1] - x[0] - m

@MihaniX · 08.04.2014, 18:53 **[ТС]**

Не работает

@gng · 08.04.2014, 21:03

Сообщение от MihaniX

Не работает

Что конкретно не работает?

Bash
1
2
3
4
$ python nailes.py 
6
[0,1,4,10,12,20]
14

@MihaniX · 11.04.2014, 20:54 **[ТС]**

Тестовая система пишет что слишком долго работает программа...

@gng · 11.04.2014, 23:36

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random
 
def maxl (i):
    if i > n-3:
        return 0
    if m[i] == 0:
        m[i]= x[i+1] - x[i] + max (maxl (i+2), maxl (i+3));
    return m[i]
 
n=100
x= sorted ([random.randrange(1000) for i in range (n)])
 
m= [0 for i in range (n)]
print x[-1] - x[0] - max( maxl(1),maxl (2))

@MihaniX · 13.04.2014, 21:32 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
def maxl (i):
    if i > n-3:
        return 0
    if m[i] == 0:
        m[i]= x[i+1] - x[i] + max (maxl (i+2), maxl (i+3));
    return m[i]
 
n=int(input())
x= list(map(int, input().split()))
 
m= [0 for i in range (n)]
print (x[-1] - x[0] - max( maxl(1),maxl (2)))

Вот такой код отправил. Правильные только первый и последний ответы... Может с тестовой системой что-то не так?

@gng · 14.04.2014, 13:14

Сообщение от MihaniX

x= list(map(int, input().split()))

Входной список нужно отсортировать по возрастанию.
Если не пройдет, то хорошо бы найти хотя бы один набор данных, дающий сбой.
Визуально ошибки я не вижу.

@MihaniX · 14.04.2014, 13:55 **[ТС]**

Да, я про это забыл. Все, задача принята. Огромное спасибо!!!

@irthgr · 15.05.2021, 16:43

Можете прислать, что у вас получилось?

@iSmokeJC · 15.05.2021, 17:08

irthgr, ты дату видел?

@irthgr · 15.05.2021, 17:51

только щас понял, но мне очень нужно! Что делать?

@КулХацкеръ · 15.05.2021, 19:59

Почитать про функцию sort и добавить ее в нужное место в последнем коде.

@haha helper · 30.06.2021, 11:33

вот код

Python
1
2
3
4
5
6
7
8
9
10
11
12
def maxl (i):
    if i > n-3:
        return 0
    if m[i] == 0:
        m[i]= x[i+1] - x[i] + max (maxl (i+2), maxl (i+3));
    return m[i]
 
n=int(input())
x= list(map(int, input().split()))
x=sorted(x)
m= [0 for i in range (n)]
print (x[-1] - x[0] - max( maxl(1),maxl (2)))

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@MihaniX 140 / 50 / 2 Регистрация: 06.08.2013 Сообщений: 292 Записей в блоге: 4

	Задача на динамику 30.03.2014, 15:41. Показов 31658. Ответов 14 Метки нет (Все метки) Помогите решить задачу на динамическое программирование. В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна. Формат входных данных В первой строке входных данных записано число N — количество гвоздиков (2<=N<=100). В следующей строке заданы N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000). Формат выходных данных Выведите единственное число — минимальную суммарную длину всех ниточек. Задали на кружке, решить не получается 0

@MihaniX 140 / 50 / 2 Регистрация: 06.08.2013 Сообщений: 292 Записей в блоге: 4
	06.04.2014, 17:04 [ТС]
	апп 0

@MihaniX 140 / 50 / 2 Регистрация: 06.08.2013 Сообщений: 292 Записей в блоге: 4
	08.04.2014, 18:53 [ТС]
	Не работает 0

@MihaniX 140 / 50 / 2 Регистрация: 06.08.2013 Сообщений: 292 Записей в блоге: 4
	11.04.2014, 20:54 [ТС]
	Тестовая система пишет что слишком долго работает программа... 0

@MihaniX 140 / 50 / 2 Регистрация: 06.08.2013 Сообщений: 292 Записей в блоге: 4
	14.04.2014, 13:55 [ТС]
	Да, я про это забыл. Все, задача принята. Огромное спасибо!!! 0

@irthgr 24 / 21 / 2 Регистрация: 15.05.2021 Сообщений: 57
	15.05.2021, 16:43
	Можете прислать, что у вас получилось? 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	15.05.2021, 17:08
	irthgr, ты дату видел? 1

@irthgr 24 / 21 / 2 Регистрация: 15.05.2021 Сообщений: 57
	15.05.2021, 17:51
	только щас понял, но мне очень нужно! Что делать? 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	15.05.2021, 19:59
	Почитать про функцию sort и добавить ее в нужное место в последнем коде. 0

Задача на динамику

Решение