Вопрос по информатике:
Задача
В. "Гвоздики"
На
прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой.
Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому
гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек
была минимальна.
Формат входного файла В первой строке входного файла INPUT.
IN записано число N – количество гвоздиков (2 ≤ N ≤ 100). В следующей строке
записано N чисел -координаты всех гвоздиков (неотрицательные целые числа,не
превосходящие 10000).
Формат выходного файла
В выходной файл OUTPUT. OUT нужно вывести единственное
число -минимальную суммарную длину всех ниточек.
Примеры:
INPUT. IN
OUTPUT. OUT
5
4
10 0 12 2
6
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 27.08.2017 10:17
- Информатика
- remove_red_eye 9471
- thumb_up 28
Ответы и объяснения 1
//PascalABC.NET версия 3.2, сборка 1389
//Если программа не запускается, то обновите версию
begin
var n := ReadInteger('n =');
var a := ReadArrInteger('Массив', n);
a.Sort;
// Println(a);
var b := ArrFill(n + 1, 0);
b[0] := 0;
b[1] := Maxint;
for var i := 2 to n do
b[i] := min(b[i - 1], b[i - 2]) + abs(a[i - 1] - a[i - 2]);
// Println(b);
WriteLn(b[n]);
end.
- 28.08.2017 08:38
- thumb_up 48
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.