Реферат: Динамическое программирование, алгоритмы на графах

c диаграммой смежности j

и оканчивающиеся цветом k}

begin

total[i mod 2, k, j]:= 0;

for l:= 1 to 3 do

{цикл по конечному цвету

полосок длины i - 1}

if magic[k, l] and j <> 0 then

{цвета l и k могут соседствовать

согласно диаграмме смежности j}

begin

total[i mod 2, k, j]:=

total[i mod 2, k, j] +

total[1 - i mod 2, l, j];

total[i mod 2, k, j]:=

total[i mod 2, k, j] +

total[1 - i mod 2, l, j - magic[k, l]]

end

end;

answer:= 0;

{суммируем количество полосок с диаграммой

смежности code и различными окончаниями}

for i:=1 to 3 do

answer:=answer + total[n mod 2, i, code];

writeln(answer:0:0)

end.

Похожая задача (“Симпатичные узоры”) предлагалась и на I-ой Всероссийской командной олимпиаде по программированию. Ее условие и решение можно прочитать в [2].

Задача 11 . Паркет (Задача VI Всероссийской олимпиады по информатике, 1994 г. )

Комнату размером N ´M единиц требуется покрыть одинаковыми паркетными плитками размером 2´1 единицу без пропусков и наложений (1 £N £ 20, 1 £M £ 8). Требуется определить количество всех возможных способов укладки паркета для конкретных значений N и M .