Решение задачи Возрастающие числа

Тема: динамическое программирование

Все возможные "возрастающие числа" занесем в массив `"num"` в лексикографическом порядке:

type numinf=record val,len:longint; end;
const num:array[1..39] of numinf=(
(val:1;len:2),(val:123;len:4),(val:1234;len:4),
  (val:12345;len:4),(val:123456;len:4),(val:12;len:3),
(val:2;len:2),(val:234;len:4),(val:2345;len:4),
  (val:23456;len:4),(val:234567;len:4),(val:23;len:3),
...
(val:8;len:2),(val:89;len:3),
(val:9;len:2));

Минимальную длину будем получать в массиве `"minlen"`:

  minlen:array[0..1000000] of longint;

который нужно инициализировать следующим образом:

for i:=1 to n do { для значений, которые еще не обработаны }
  minlen[i]:=1000000; { установить достаточно большое число }
minlen[0]:=0; { 0 можно получить с помощью строки нулевой длины }

Теперь, двигаясь по таблице от 0 до `n`, узнаем самую короткую длину разложения числа `i` на возрастающие числа. Используется принцип динамического программирования: из оптимального решения подзадач можно получить оптимальное решение всей задачи.

for i:=0 to n do
  begin
    { добавляем к лучшему способу получения числа i
      все возможные возрастающие числа }
    for j:=1 to 39 do
      begin
        k:=i+num[j].val;
        { получаем новый способ получения числа k }
        if (k<=n) and (minlen[k]>minlen[i]+num[j].len) then
           { если длина этого способа меньше, запоминаем его в массиве }
          minlen[k]:=minlen[i]+num[j].len;
      end;
  end;

Обратная трассировка по массиву `"minlen"`:

s:='';
while n>0 do
  begin
    { рассматриваем возрастающие числа в лексикографическом порядке }
    for j:=1 to 39 do
      begin
        k:=n-num[j].val;
        if (k>=0) and (minlen[k]+num[j].len=minlen[n]) then
          { если с помощью этого числа получается способ,
            дающий нужную минимальную длину, 
            то используем именно это число }
          begin
            { добавляем возрастающее число к строке-результату }
            str(num[j].val,ss);
            if length(ss)<=2 then
              s:=s+ss+'+'
            else
              s:=s+ss[1]+'-'+ss[length(ss)]+'+';
            n:=k; { уменьшаем искомое число на возрастающее число }
            break;
          end;
      end;
  end;
{ выводим строку-результат без последнего символа '+' }
writeln(copy(s,1,length(s)-1));