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

Довольно часто на олимпиадах встречаются задачи, которые можно решать используя алгоритмы перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого подхода. Для решения таких задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи решается похожая, но более простая. При этом осуществляется переход к еще более простым и так далее, пока не доходят до тривиальной. Из предыдущего рассуждения видно, что решение можно оформить рекурсивно. Но простое применение этого приема очень легко может привести к переполнению стека. Необходимо позаботиться об оптимизации рекурсивных проходов и не вычислять одно и то же значение несколько раз, сделать так называемое отсечение. Можно вообще отказаться от рекурсии и решать задачу двигаясь от простых подзадач к более сложным, запоминая решения в массиве, одномерном или двумерном. Второй путь решения и называется динамическим программированием.

Для решения таких задач существует специальная теория. Большая заслуга в ее

создании принадлежит Р. Беллману. В общем виде она достаточна сложна, поэтому здесь не рассматривается. В то же время конкретные задачи, рассмотренные ниже, вполне могут понять идеи, лежащие в основе решения задач данного класса.

Рассмотрим решения следующих задач.

Задача 1 Минимальный путь в таблице или «Черепашка 1»

Задача 2 Количество способов или «Черепашка 2»

Задача 3 Лестница 1

Задача 4 Лестница 2

Задача 5 Лестница 3

Задача 6 Фишка

Задача 7 Блоха

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

Задача 9 Наибольшая возрастающая подпоследовательность

Задача 10 Деньги

Задача 11 Скобки

Задача 12 Наибольшая последовательнократная подпоследовательность

Задача 13 Лесенки

Задача 14 Шаблон и слово

Задача 15 Рюкзак 1_1

Задача 16 Рюкзак 1_2

Задача 17 Рюкзак 2

Задача 18 Свинья-копилка

Задача 19 Золотая гора

Задача 20 Стена

Задача 21 Багдадский вор

Задача 22 Максимальный квадрат

Задача 23 Большой, белый, прямоугольный

Задача 24 Марсианское ДНК

Задача 25 Два слова

Задача 26 Торговля с походом

Задача 27 Взрывоопасность на складе фейерверков

Задача 28 К-ичные числа деда Мороза

Задача 29 Что тут считать

Задача 30 Клев

Задача 31 Палиндромы

Задача 32 График работы

Задача 33 Задача о распиле палки

Задача 34 Непарралельный слалом

Задача 35 Цифровой экран

Задача 36 Искривленное пространство

Задача 37 Прямоугольное королевство

Задача 1. Минимальный путь в таблице или «Черепашка»

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале черепашка находится в левой верхней клетке. За один ход ей разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с черепашки берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

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

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M натуральных чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

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

В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол и в следующих n+m-1 строках координаты клеток, через которые пройдет черепашка

Пример

Input.txt	Output.txt
3 4 1 1 1 1 5 2 2 100 9 4 2 1	8 1 1 1 2 2 2 3 2 3 3 3 4

Заведем двумерный массив такого же размера, что и данный. Назовем данный массив «а», а второй массив «b».

Алгоритм решения будет следующим:

1. копируем элемент а[1,1] элемент b[1,1].

2. Заполняем первую строку матрицы b. Так как движение возможно только слева направо, то черепашка отдаст все деньги, записанные в клетках матрицы «а».

3. Точно так же заполняем первый столбец. Здесь движение возможно только сверху вниз.

4. Заполняем остальную часть матрицы построчно. В элемент a[i,j] мы можем попасть или сверху, тогда уплаченная сумма будет b[i-1,j]+a[i,j] или слева, тогда уплаченная сумма будет b[i,j-1]+a[i,j]. Из двух вариантов выбираем лучший, то есть меньший.

5. Ответом будет число в ячейке матрицы b[n,m].

program cherep;

{$APPTYPE CONSOLE}

Uses SysUtils;

const nmax=100;

const mmax=100;

var a,b,c:array[1..nmax,1..mmax]of integer;

i,j,s1,s2,n,m:integer;

procedure putj(i1,j1:integer); // выводит путь от начала к концу

begin

if (i1=1)and(j1=1) then exit

else // если дошли до начала, то выходим из процедуры

if c[i1,j1]=1 then dec(j1) //если пришли слева, то уменьшаем j

else dec(i1); // если пришли справа, то уменьшаем i

putj(i1,j1); //и вызываем рекурсивно саму процедуру

writeln(i1,' ',j1); // на подъеме выводим путь

end;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

read(n,m); // считываем размеры массива

for i:=1 to n do // считываем массив

for j:=1 to m do

6. read(a[i,j]);

7. b[1,1]:=a[1,1]; // берем монеты из первой клетки

8. for j:=2 to m do // проходим по первой строке

9. begin

10. b[1,j]:=b[1,j-1]+a[1,j]; // заполняем первую строку

11. c[1,j]:=1; //направление прихода 1 -слева

12. end;

13. for i:=2 to n do // заполняем первый столбец

14. begin

15. b[i,1]:=b[i-1,1]+a[i,1];

16. c[i,1]:=2; // направление прихода 2- сверху

17. end;

18. for i:=2 to n do

19. for j:=2 to m do

20. begin

21. s1:=b[i-1,j]+a[i,j]; // набранная сумма, если пришли сверху

22. s2:=b[i,j-1]+a[i,j]; // набранная сумма, если пришли слева

23. if s1<s2 // если да, то берем s1 иначе s2

24. then

25. begin b[i,j]:=s1;c[i,j]:=2;end //записываем в массив с 1

26. else

27. begin b[i,j]:=s2;c[i,j]:=1; end ; //записываем в массив с 2

28. end;

29. writeln(b[n,m]); // выводим мин. сумму

30. putj(n,m); //выводим путь

31. write(n,' ',m);

32. close(input);

33. close(output);

34. end.динампрогрзадачи

Задача 2 Количество способов или Черепашка 2

Дана прямоугольная таблица размера NxM. Черепашка находится в левой верхней клетке. За один ход ей разрешается перемещаться в соседнюю клетку либо вправо, либо вниз .

Требуется найти количество путей, которыми черепашка может попасть в правый нижний угол.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20).

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

В выходной файл запишите количество способов, которыми можно попасть в правый нижний угол.

Пример

Input.txt	Output.txt
3 4	10

 Алгоритм решения практически тот же самый. Отличия от предыдущего алгоритма понятны из пояснений к решению.

program kolspocobov;

const nmax=20;mmax=20;

Var a:array[1..nmax,1..mmax] of longint;

i,j,n,m:integer;

Begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n,m);

for i:=1 to n do a[i,1]:=1; попасть в клетки первого столбца можно одним

способом

for j:=1 to m do a[1,j]:=1; попасть в клетки первой строки можно одним

способом

for i:=2 to n do в другие клетки можно попасть или сверху или

слева

for j:=2 to m do

a[i,j]:=a[i-1,j]+a[i,j-1]; суммируем количество способов

write(a[n,m]); выводим результат

close(output);

End.

Дополнительное задание: выяснить, при каких размерах таблицы результат превысит тип longint и как выйти из положения.

динампрогрзадачи

Задача 3 Лестница 1

Определить, сколькими различными способами можно подняться на N-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну.

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

Во входном файле задано одно число N (1<=N<=100).

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

В выходной файл содержит количество различных способов подъема на N-ю ступеньку.

Пример.

Input.txt	Output.txt
5	8

Решение. Пусть K(N) –количество способов подъема на N ступенькую. Исходя из условия задачи, на N ступеньку можно подняться непосредственно с N-1-й и N-2-й ступенек. Поэтому, если мы знаем количество способов подъема K(N-1) и K(N-2) на N-1 и N-2 ступеньки соответственно, то количество способов подъема на N ступеньку может быть определено как K(N) = K(N-2) + K(N-1).

Такое соотношение получается потому, что любой способ подъема на N-2-ю ступеньку превращается в способ подъема на N-ю ступеньку добавлением перешагивания через N-1-ю ступеньку, а любой способ подъема на N-1-ю ступеньку превращается в способ подъема на N-ю ступеньку добавлением подъема с N-1 на N-ю ступеньку. Все эти способы различны. Аналогичное соотношение справедливо для любой ступеньки i, начиная с третьей, т.е.

K(i) = K(i – 2) + K(i – 1)

Осталось определить значения K(1) и K(2), которые равны: K(1) = 1, K(2) = 2.

Следовательно, для решения задачи достаточно одномерного массива с N  элементами.

K[1]: = 1;

K[2]: = 2;

For i:=3 to n do

K[i]: = K[i – 1] + K[i – 2];

И даже массив нам не нужен. Достаточно использовать три переменные a,b,c.

a:=1;b:=1;

For i:=3 to n do

begin

c:=a+b;

a:=b;

b:=c

end;

И мы получаем последовательность чисел Фибоначчи. В частных случаях при n=1 и n=2 программа работать не будет и тогда есть два выхода.

Первый: рассмотреть частный случай if (n=1)or(n=2) then begin write(n);halt(0) end; т.е. вывести результат и прервать работу программы.

Второй : взять a=1; b=0; и цикл

for i:=1 to n do

begin

c:=a+b;

a:=b;

b:=c

end;

Если N достаточно большое, то количество цифр в числе Фибоначчи превысит разрядность всех числовых типов и надо будет использовать длинную арифметику.

program lestnica1;

const nmax=1000;

var a,b,c:array[0..nmax] of byte;

n,um,i,j,kol:integer;

procedure summa; сложение двух длинных чисел

var um,i:integer;

begin

if a[0]>b[0] находим слагаемое с большим количеством

then kol:=a[0] цифр

else kol:=b[0];

um:=0;

for i:=1 to kol do складываем два длинных числа

begin

c[i]:=(a[i]+b[i]+um) mod 10; цифра результата

um:=(a[i]+b[i]+um) div 10; то что в уме

end;

if um>0 если после сложения в уме осталась цифра

then

begin

inc(kol); c[kol]:=um; записываем ее в сумму

end;

c[0]:=kol; запоминаем количество цифр

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

a[0]:=1;a[1]:=1;

b[0]:=1;b[1]:=2;

if (n=1)or(n=2) then

begin write(n);close(output);halt(0) end; частный случай

for j:=3 to n do ищем n-е число Фибоначчи

begin

fillchar(c,sizeof(c),0);

summa; находим сумму двух

предыдущих

a:=b; копируем массив b в а

b:=c; с в b

end;

for i:=kol downto 1 do выводим результат

write(c[i]);

close(output);

close(input);

end.

динампрогрзадачи

Задача 4 Лестница 2

Определить, сколькими различными способами можно подняться на N-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну и на лестнице есть площадка, на которой можно отдохнуть.

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

Во входном файле задано натуральные числа N– количество ступенек на лестнице и M номер площадки (1<=M<=N<=100).

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

Выходной файл содержит количество различных способов подъема на N-ю ступеньку.

Пример.

Input.txt	Output.txt
5 3	6

Площадкой лестница делится на две лестницы меньших длин. Длина первой лестницы равна m, а длина второй n-m. Найдем количество способов подъема по каждой лестнице и перемножим полученные числа, так как каждый способ подъема по первой лестнице сочетается с каждым способом подъема по второй. При больших значениях N придется использовать длинную арифметику для сложения и умножения длинных чисел.

program lestnica2;

const nmax=1000;

var a,b,c,d,e:array[0..nmax] of byte;

dv,n,um,i,j,kol,m:integer;

procedure out;

var i:integer;

begin

assign(output,'output.txt');

rewrite(output);

for i:=c[0] downto 1 do

write(c[i]);

close(output);

end;

procedure summa(k:integer);

var um,i:integer;

begin

fillchar(c,sizeof(c),0);

a[0]:=1;a[1]:=1;

b[0]:=1;b[1]:=2;

if a[0]>b[0]

then kol:=a[0]

else kol:=b[0];

if k=1 then begin c:=a;exit end;

if k=2 then begin c:=b;exit end;

for j:=3 to k do

begin

um:=0;

for i:=1 to kol do

begin

c[i]:=(a[i]+b[i]+um) mod 10;

um:=(a[i]+b[i]+um) div 10;

end;

if um>0

then begin inc(kol); c[kol]:=um; end;

c[0]:=kol;

a:=b;

b:=c;

end;

end;

Procedure umnoj;

Begin

fillchar(c,sizeof(c),0);

for i:=1 to e[0] do

for j:=1 to d[0] do

begin

dv:=e[i]*d[j]+c[i+j-1];

inc(c[i+j],dv div 10);

c[i+j-1]:=dv mod 10;

end;

c[0]:=e[0]+d[0];

while (c[0]>1)and(c[c[0]]=0)

do dec(c[0]); находим количество цифр в результате

End;

begin

assign(input,'input.txt');

reset(input);

read(n,m);

summa(m);

d:=c;

if n-m>0

then summa(n-m)

else begin c[0]:=1;c[1]:=1;end;

e:=c;

umnoj;

out;

close(input);

end.

динампрогрзадачи

Задача 5 Лестница 3

Определить, сколькими различными способами можно подняться на K-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну и на лестнице есть площадка, на которой можно отдохнуть.

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

Во входном файле задано натуральные числа N- количество ступенек на лестнице, M- номер площадки (1<=M<=N<=100) и К- номер ступеньки, на которую надо подняться (1<=K<=100).

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

Выходной файл содержит количество различных способов подъема на K-ю ступеньку.

Пример.

Input.txt	Output.txt
10 5 3	3

В этой задаче могут быть два случая. Если К<=М, то мы получаем задачу «Лестница 1». Если Если К>М, то задачу «Лестница 2».

динампрогрзадачи

Задача 6 Фишка

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более T. Найти число различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.

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

Во входном файле заданы два числа N и T. (1<=T<=N<=100).

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

Выходной файл содержит количество различных способов достижения N-й ступеньки.

Пример

Input.txt	Output.txt
4 2	4

Понятно, что алгоритм решения задачи аналогичен алгоритму решения задачи «Лестница 1», в которой Т=2. Первые T элементов масива заполняем, складывая все значения предыдущих элементов.

a[1]: = 1;a[2]: = 1;

For i:=3 to T do

For j:=1 to i-1 do

a[i]: = a[i ] + a[j]

А значения элементов, начиная с T+1 равны сумме T предыдущих элементов.

For i:=j-T to j-1 do

a[j]: = a[j ] + a[i]

Для того, чтобы заполнить массив одним циклом поступим следующим образом. Добавим в массив слева фиктивные сто элементов равные нулю. Массив опишем так a:array[-99.. 100] of longint.

И решение будет такое:

a[1]: = 1;a[2]: = 1;

For i:=3 to n do

a[i]: = 2*a[i-1 ] - a[i-t-1]

динампрогрзадачи

Задача 7 Блоха

Электронная блоха прыгает по дорожке, которая поделена на N клеток, причём они пронумерованы по порядку числами от 1 до N. Из клетки с номером i блоха может прыгнуть вперёд не более чем на C_i клеток, затратив при этом энергию V_i.Требуется написать программу для блохи, которая находила бы маршрут, требующий наименьшей энергии и приводящей блоху из клетки с номером 1 в клетку с номером N.

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

В первой строке входного файла записано число N (0 < N<= 200000). Далее в (i+1)-й строке записана информация о i-й клетке – два целых числа Ci и Vi (0 <= Ci <= 100, 0 <= Vi <= 10000).

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

В первую строку входного файла необходимо вывести число V – минимальное количество энергии, которое необходимо блохе, чтобы пропрыгать путь от клетки 1 до клетки N.

Пример

Input.txt	Output.txt
4 2 1 2 2 2 0 2 4	1

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

program bloxa1;

const nmax=200000;

var a,c,v:array[1..nmax] of longint;

n,i,j:longint;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

for i:=1 to n do заполняем массив а большим числом

a[i]:=maxint;

for i:=1 to n do

read(c[i],v[i]);

a[1]:=0;

for i:=2 to n do перебираем возможные способы

добраться до i-ой ступеньки

for j:=1 to i-1 do

if (j+c[j]>=i)and(a[j]+v[j]<a[i])

then a[i]:=a[j]+v[j];

write(a[n]); выводим результат

close(input);

close(output);

end.

Если в задаче потребуется вывести номера клеток, по которым будет прыгать блоха, то поступим следующим образом: заведем массив b. В клетках этого массива запишем номера клеток откуда прыгнула блоха и путь выведем рекурсивно. Тогда программа будет следующая.

program bloxa2;

const nmax=200000;

var a,c,v:array[1..nmax] of longint;

n,i,j:longint;

procedure rec(k:integer);

begin

if k=0 then exit;

rec(b[k]);

write(k,’ ‘);

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

for i:=1 to n do заполняем массив а большим числом

a[i]:=maxint;

for i:=1 to n do

read(c[i],v[i]);

a[1]:=0;

for i:=2 to n do перебираем возможные сособы

добраться до i-ой ступеньки

for j:=1 to i-1 do

if (j+c[j]>=i)and(a[j]+v[j]<a[i])

then a[i]:=a[j]+v[j];

writeln(a[n]); выводим результат

rec(n); вызываем рекурсивную процедуру вывода пути

close(input);

close(output);

end.

динампрогрзадачи

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

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

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

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

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

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

Пример

Input.txt	Output.txt
5 4 10 0 12 2	6

Чтобы было выполнено условие задачи необходимо, чтобы первый гвоздик был связан со вторым, а последний с предпоследним. Для того, чтобы ниточка была привязана к первому гвоздику введем фиктивный нулевой гвоздик и расстояние от него до самого себя сделаем равным нулю, а расстояние от нулевого до первого возьмем бесконечно большим. Для наших ограничений достаточно 30000. Полученную длину ниточек будем хранить в массиве b. Пусть последний текущий гвоздик имеет номер k. Он обязательно привязан к гвоздику с номером k-1.

Может быть два варианта:

1. гвоздики с номерами k-2 и k-1 связаны ниточкой. Тогда общая длина ниточек равна

b[k-1]+a[k]-a[k-1].

2. гвоздики с номерами k-2 и k-1 не связаны ниточкой. Тогда общая длина ниточек равна

b[k-2]+a[k]-a[k-1].

Длины последней ниточки, связывающей предпоследний и последний гвоздики и ниточки, связывающей первый и второй гвоздики, автоматически прибавятся к полученной ранее сумме.

program gvozdiki;

const nmax=100;

var d,k,n,i,j:integer;

a:array[1..nmax] of integer;

b:array[0..nmax] of integer;

procedure init;

var p: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-1 do сортируем гвоздики по возрастанию

for j:=i+1 to n do

begin

if a[i]>a[j] then

begin

p:=a[i];

a[i]:=a[j];

a[j]:=p;

end;

end;

close(input);

end;

function min(x,y:integer):integer; находит минимальное из двух чисел

begin

if x<y then

min:=x

else min:=y;

end;

procedure solve;

begin

b[0]:=0; фиктивный нулевой гвоздик

b[1]:=30000; расстояние от фиктивного до первого

равно бесконечности

for i:=2 to n do перебираем гвоздики

begin

b[i]:=min(b[i-1],b[i-2])+a[i]-a[i-1]; выбираем минимальное из двух

возможных длин

end;

end;

procedure out;

begin

write(b[n]);

close(output);

end;

begin init; solve; out;end.

динампрогрзадачи

Задача 9 Наибольшая возрастающая подпоследовательность

Для заданной числовой последовательности A[1.. N] найти наибольшую возрастающую подпоследовательность не обязательно идущих подряд, но обязательно идущих в порядке увеличения индексов элементов и ее длину . Для возрастающей подпоследовательности (a_i, a_j, …, a_k) верно, что a_i< a_j< …< a_k, когда i < j < k.