Начало
Соревнования
Разбор задачи H. Сдача
Тема: динамическое программирование, сложение и вывод длинных целыхСложность: средняя
Для сдачи суммы i монетами номиналом b1, …, bj есть следующие варианты:
- 0 монет номиналом bj: способ сдать сумму i монетами номиналом b1, …, bj-1;
- 1 монета номиналом bj: bj + способ сдать сумму i-bj монетами номиналом b1, …, bj-1;
- …
- k= ⌊ i/bj ⌋ монет номиналом bj: k⋅bj + способ сдать сумму i-k⋅bj монетами номиналом b1, …, bj-1.
Чтобы получить количество способов сдать сумму i монетами номиналом b1, …, bj, нужно просуммировать количество способов сдать сумму i-k⋅bj монетами номиналом b1, …, bj-1 для k от 0 до ⌊ i/bj ⌋.
Количество способов будем хранить в таблице T[i, j], где i – сумма сдачи, j – номер последнего использованного номинала.
T[0,0] = 1
T[i,0] = 0, если i>0
T[i, j] = ⌊ i/bj ⌋∑k=0 T[i-k⋅bj, j-1], если j>0
Вычисления можно существенно ускорить, используя следующее упрощение:
T[i, j] = ⌊ i/bj ⌋∑k=0 T[i-k⋅bj, j-1] = T[i,j-1] + ⌊ i/bj ⌋∑k=1 T[i-k⋅bj, j-1] = T[i,j-1] + ⌊ i/bj ⌋-1∑k=0 T[i-bj-k⋅bj, j-1] = T[i,j-1] + T[i-bj, j]
Вместо матрицы для хранения результатов можно использовать вектор:
T[i]=T[i]+T[i-bj], для i от bj до S.
Так как результат может быть очень большим, для вычислений нужно использовать длинную арифметику.
const mysize=25;
type mylong=array[1..mysize] of integer;
{ сложение длинных целых чисел }
procedure add(var a,b:mylong);
var i,p:integer;
begin
p:=0; { перенос }
for i:=1 to mysize do
begin
p:=p+a[i]+b[i];
b[i]:=p mod 10;
p:=p div 10;
end;
end;
{ вывод длинных целых чисел }
procedure print(var a:mylong);
var i:integer;
flg:boolean;
begin
flg:=false; { была ненулевая цифра? }
for i:=mysize downto 1 do
begin
if a[i]<>0 then
flg:=true;
if flg or (i=1) then
write(a[i]);
end;
end;
Основная часть программы выглядит так:
var T:array[0..10000] of mylong;
b:array[1..10] of integer;
i,j,n,s:integer;
...
read(s,n);
for i:=1 to n do
read(b[i]);
T[0][1]:=1;
for j:=1 to n do
for i:=b[j] to s do
add(T[i-b[j]],T[i]);
print(T[s]);
