Динамическое программирование , гвозди

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Формат входных данных:
В первой строке входного файла записано число N - количество гвоздиков (1 N 100). В следующей строке записано
N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек.
Помогите, пожалуйста

function min(a,b:integer):integer;
begin
  if a<b then min := a
  else min := b;
end;
 
procedure Swap(var a,b:integer);
var
  q:integer;
begin
  q := a;
  a := b;
  b := q;
end;
 
var
  n,i,j:integer;
  a,b:array[-1..100] of integer;
begin
  assign(input,'input.txt'); reset(input);
  assign(output,'output.txt'); rewrite(output);
  Read(n);
  for i := 1 to n do Read(a[i]);
  for i := 1 to n do
    for j := i+1 to n do
      if a[i]>a[j] then Swap(a[i],a[j]);
  a[0] := Maxint;
  a[-1] := 0;
  for i := 1 to n do
    b[i] := min(b[i-1],b[i-2])+abs(a[i]-a[i-1]);
  WriteLn(b[n]);
  close(input); close(output);
end.

Arsuit
Спасибо . Суперски помог.

Arsuit
Спасибо еще раз. Забыл войти

Цитата Arsuit @ 17.04.06, 11:53

function min(a,b:integer):integer;
begin
  if a<b then min := a
  else min := b;
end;
 
procedure Swap(var a,b:integer);
var
  q:integer;
begin
  q := a;
  a := b;
  b := q;
end;
 
var
  n,i,j:integer;
  a,b:array[-1..100] of integer;
begin
  assign(input,'input.txt'); reset(input);
  assign(output,'output.txt'); rewrite(output);
  Read(n);
  for i := 1 to n do Read(a[i]);
  for i := 1 to n do
    for j := i+1 to n do
      if a[i]>a[j] then Swap(a[i],a[j]);
  a[0] := Maxint;
  a[-1] := 0;
  for i := 1 to n do
    b[i] := min(b[i-1],b[i-2])+abs(a[i]-a[i-1]);
  WriteLn(b[n]);
  close(input); close(output);
end.

к сожелению я не компилятор и ваш код не понял.

Не могли бы вы описать алгоритм, дать док-во правильности его работы. И привести оценку временной сложности.

DistMaster

Я опять не понял твое задание Если гвоздики расположены на прямой, то длинна всех ниточек будет минимальна если соеденять только сосение гвоздики? Или я не прав? В чем проблема?

Цитата DistMaster @ 17.04.06, 09:19

Требуется соединить какие-то пары гвоздиков ниточками

Цитата DistMaster @ 17.04.06, 09:19

так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка

А если я свяжу какую-то рядом стоящую пару гвоздиков ниточками, а к остальным привяжу оооооочень маленькие ниточки, условие задачи будет выполнено?

Сообщение отредактировано: Maks1986 - 17.04.06, 15:26

Maks1986
Ну, во-первых, расстояние между гвоздями разное.
Например
координаты гвоздей
1 3 4 7 8 10 12
А вот ответ
1-3-4 7-8 10-12
4 гвоздь не нужно соединять с 7, 8 - с 10
Не знаю, доступно ли я объяснил, но я тоже не совсем понял чего ты не понял

DistMaster
Тогда, если я тебя правильно понял и нигде не прогнал, то это будет выглядеть примерно так:

begin
 
{загоняешь координыти в массив и сортируешь его}
 
sum:=(a[2]-a[1])+(a[n]-a[n-1]);
i:=3;
while i<(n-1) do
   if (a[i]-a[i-1])<(a[i+1]-a[i]) then
              begin
              sum:=sum+(a[i]-a[i-1]);
              i:=i+1;
              end
                     else
                     begin
                     sum:=sum+(a[i+1]-a[i]);
                     i:=i+2;
                     end;
end.

Maks1986
Ну вроде, да. Хотя не знаю, надо проверить. А что выше указанный код тебя не устроил? Решил сам. Предыдущий код точно верен. Но все-равно Спасибо!