Задача В. "Гвоздики" На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а сум...
Задача
В. "Гвоздики"
На
прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой.
Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому
гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек
была минимальна.
Формат входного файла В первой строке входного файла INPUT.
IN записано число N – количество гвоздиков (2 ≤ N ≤ 100). В следующей строке
записано N чисел -координаты всех гвоздиков (неотрицательные целые числа,не
превосходящие 10000).
Формат выходного файла
В выходной файл OUTPUT. OUT нужно вывести единственное
число -минимальную суммарную длину всех ниточек.
Примеры:
INPUT. IN
OUTPUT. OUT
5
4
10 0 12 2
6
Гость
Ответ(ы) на вопрос:
Гость//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.
Не нашли ответ?
Похожие вопросы