Задача Гвоздики

@KIROSIL · Регистрация: 09.06.2022

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

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

Входные данные

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

Выходные данные

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

Примеры
Ввод
Вывод
6
3 4 6 12 13 14
5

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    int a[n];
    int b;
    int c=0;
    for(int i=0;i<n;i++)
    {cin>>b;
        a[i]=b;
    }
     for(int i=0;i<n;i++)
    {if (i==0)
    {
        c+=(a[i+1]-a[i]);
        i+=1;
    }
    else if (i==n)
    {c+=(a[i]-a[i-1]);
    }
    else if (a[i]-a[i-1]>a[i+1]-a[i])
    {
        c+=(a[i+1]-a[i]);
        i+=1;
    }
    else
    {
        c+=(a[i]-a[i-1]);
    }
    }
if(n==1)
{
    cout<<1;
}
else    
 {       
    
cout<<c;
}
    return 0;
}

Понимаю, что код громоздкий, но с моими примерами он работал. На сайте тест заваливает. Не пойму почему

@mr-Crocodile · 09.06.2022, 17:19

KIROSIL, ты уверен, что раздел "Pascal (Паскаль)" подходит для твоей темы лучше всего?

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

Добавлено через 9 минут
тут, например, подробный разбор задачи с картинками...
(ссылку взял тут на форуме из темы: Динамическое программирование, гвоздики )

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка 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 и т. д. Сборка примера Скачайте. . .

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,381
	09.06.2022, 17:19
	KIROSIL, ты уверен, что раздел "Pascal (Паскаль)" подходит для твоей темы лучше всего? ну и задача то классическая, на ДП. Посмотри похожие темы внизу. Там есть и решения и разбор. Добавлено через 9 минут тут, например, подробный разбор задачи с картинками... (ссылку взял тут на форуме из темы: Динамическое программирование, гвоздики ) 0