Подразделы

Другие разделы

Дата и время

05/04/2025 19:47:43

Авторизация

Зарегистрироваться
Восстановить пароль

Разбор задачи 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]);

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Разбор задачи H. Сдача