Начало
Соревнования
Разбор задачи H. Сдача
Тема: динамическое программирование, сложение и вывод длинных целыхСложность: средняя
Для сдачи суммы `i` монетами номиналом `b_1,\ …,\ b_j` есть следующие варианты:
- 0 монет номиналом `b_j`: способ сдать сумму `i` монетами номиналом `b_1,\ …,\ b_{j-1}`;
- 1 монета номиналом `b_j`: `b_j\ +` способ сдать сумму `i-b_j` монетами номиналом `b_1,\ …,\ b_{j-1}`;
- …
- `k=\ ⌊\ i//b_j\ ⌋` монет номиналом `b_j`: `k*b_j\ +` способ сдать сумму `i-k*b_j` монетами номиналом `b_1,\ …,\ b_{j-1}`.
Чтобы получить количество способов сдать сумму `i` монетами номиналом `b_1,\ …,\ b_j`, нужно просуммировать количество способов сдать сумму `i-k*b_j` монетами номиналом `b_1,\ …,\ b_{j-1}` для `k` от 0 до `⌊\ i//b_j\ ⌋`.
Количество способов будем хранить в таблице `T[i,\ j]`, где `i` – сумма сдачи, `j` – номер последнего использованного номинала.
`T[0,0]\ =\ 1`
`T[i,0]\ =\ 0`, если `i>0`
`T[i,\ j]\ =\ sum_{k=0}^{⌊\ i//b_j\ ⌋}\ T[i-k*b_j,\ j-1]`, если `j>0`
Вычисления можно существенно ускорить, используя следующее упрощение:
`T[i,\ j]\ =\ sum_{k=0}^{⌊\ i//b_j\ ⌋}\ T[i-k*b_j,\ j-1]\ =\ T[i,j-1]\ +\ sum_{k=1}^{⌊\ i//b_j\ ⌋}\ T[i-k*b_j,\ j-1]\ =\ T[i,j-1]\ +\ sum_{k=0}^{⌊\ i//b_j\ ⌋-1}\ T[i-b_j-k*b_j,\ j-1]\ =\ T[i,j-1]\ +\ T[i-b_j,\ j]`
Вместо матрицы для хранения результатов можно использовать вектор:
`T[i]=T[i]+T[i-b_j]`, для `i` от `b_j` до `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]);
