Нельзя перебрать все подмножества, их всего 2⁵⁰⁰. Максимальное значение суммы 50000. Найдем все возможные значения сумм. Заполним массив B[0..500,50000] логических значений. Положим B[L, S] = true, если можно подобрать коэффициенты k₁, k₂,..., k_L со значениями 0 и 1 так, что k₁A₁+ k ₂A₂ +...+k_LA_L= S.

При L=0 слагаемых нет, поэтому B[0,0]=true, B[0,S]=false при S от 1 до 50000. Найдем B[L,S] при L>0.

В сумму S слагаемое A_L может входить или не входить. Если слагаемое A_L входит, то k₁A₁+ k ₂A₂ +...+k_L-1A_L-1= S - A_L, если не входит, то k₁A₁+ k ₂A₂ +...+k_L-1A_L-1= S. Значит, сумму S с помощью L слагаемых можно получить одним из двух вариантов:

• получить S с помощью L-1 слагаемого;

• получить S-A_L с помощью L-1 слагаемого.

Отсюда B[L,S]=B[L-1,S] or B[L-1,S-A[L]].

На самом деле двумерный массив B не нужен, достаточно двух массивов по 50000 логических элементов для двух соседних шагов. Более того, можно обойтись одним массивом B[0..50000], заполняя его в обратном порядке.

Program Sums;

Var

N: integer;

A: array [1..100] of integer;

B: array [0..50000] of boolean; {достижимость сумм}

Fin,Fout: text;

i,k: integer;

Sum,S: integer;

Begin

Assign(Fin,'input.txt’);

Reset(Fin);

ReadLn(Fin,N);

Sum:=0; {общая сумма элементов множества}

For i:=1 to N do

begin

Read(Fin,A[i]);

Sum:=Sum+A[i]

end;

Close(Fin);

B[0]:=true;

For S:=1 to Sum do B[S]:=false; {инициализация}

For i:=1 to N do

For S:=Sum downto A[i] do

B[S]:=B[S] or B[S-A[i]];

k:=0; {счетчик}

For S:=0 to Sum do

if B[S] then k:=k+1; {новое значение суммы}

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,k);

Close(Fout);

End.

Задачи для самостоятельного решения

4.1. Прогрессия (6)

Король Камбузии с детства боится несчастливых арифметических прогрессий с разностью 13. Однажды ему представили список расходов на нужды подданных, состоящий из N чисел. Король потребовал оставить только такую начальную часть списка, в которой не скрывается несчастливая арифметическая прогрессия. Либеральная общественность, считаясь с мнением короля, настаивает, тем не менее, на сохранении как можно большей части списка. Найти максимальное значение K такое, что из первых K чисел списка невозможно выделить M чисел, следующих в порядке их нахождения в списке и образующих последовательные члены несчастливой арифметической прогрессии. Выдать члены первой обнаруженной несчастливой прогрессии.

Ввод из файла INPUT.TXT. Первая строка содержит два целых положительных числа N и M, разделенных пробелом: N – количество чисел в списке, а M – недопустимое число членов прогрессии. Вторая строка содержит список расходов в виде целых положительных чисел. Ограничения: 2 ≤ N,M ≤ 5000, 1 ≤ X_i ≤ 65000, время 2 с.

Вывод в файл OUTPUT.TXT. В первой строке выводится единственное число K- максимальное количество начальных чисел списка, не содержащих в качестве подсписка M последовательных членов несчастливой арифметической прогрессии. Во второй строке выводятся через пробел члены первой обнаруженной несчастливой прогрессии. Если ее не обнаружено, вывести No.

Пример

Ввод

9 3

5 9 3 22 16 19 35 7 29

Вывод

6

9 22 35

Пояснение: из первых 7 чисел выделяются 3 члена несчастливой прогрессии 9, 22, 35, а из первых 6 чисел можно выделить только 2 таких члена: 9, 22 либо 3, 16.

4.2. Треугольник (5)

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

7

3 8

8 1 6

4 2 3 0

Каждый шаг на пути происходит в направлении вниз по диагонали (влево или вправо). Число строк в треугольнике от 1 до 100. Треугольник составлен из целых чисел от 0 до 99.

Ввод из файла INPUT.TXT. Первое число определяет количество строк треугольника N. Далее задаются строки треугольника.

Вывод в файл OUTPUT.TXT. В первой строке выводится единственное число – наибольшая сумма. Во второй строке выдаются через пробел числа от вершины треугольника до основания, дающие наибольшую сумму. Если решений несколько, вывести любое из них.

Пример

Ввод

4

7

3 8

8 1 6

4 2 3 0

Вывод

24

7 8 6 3

4.3. Бильярд (6)

Бильярдный стол расчерчен на квадратные клетки и имеет размеры MN клеток. В углах стола находятся четыре лузы для шаров. В каждой клетке (i, j), i = 1, 2,..., M; j = 1, 2,..., N задано целое число C_ij. Шар ставится в центр одной из клеток и после удара может катиться в одном из четырех направлений вдоль диагоналей клетки. Если он достигает края стола, то отражается и продолжает движение, а если попадает в угол стола, то сваливается в лузу. Количество отражений не ограничено. Требуется выбрать начальную клетку для шара и направление удара так, чтобы

• шар попал в одну из луз;

• не пересек какую-либо клетку дважды по одной или разным диагоналям;

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

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

р начинает движение с правой нижней клетки, проходит в результате все клетки и попадает в верхнюю правую лузу.

Ввод из файла INPUT.TXT. Первая строка содержит числа M и N через пробел. Каждая i-я строка из следующих M строк содержит N чисел C_ij (1 ≤ j ≤ N).

Вывод в файл OUTPUT.TXT. В первой строке выводится максимальная сумма чисел. Во второй строке выводятся через пробел два числа: номера строки и столбца начальной клетки. Нумерация строк и столбцов начинается с 1. В третьей строке двумя заглавными латинскими буквами указывается направление удара:

• DR – вниз и направо;

• DL – вниз и налево;

• UR – вверх и направо;

• UL – вверх и налево.

Считается, что направление "вниз” соответствует увеличению номера строки, а "направо” - увеличению номера столбца.

Ограничения: 2 ≤ M ≤ 300; 2 ≤  N ≤ 300; -1000 ≤  C_ij ≤ 1000; время работы программы до 2 с.

Пример

Ввод

2 3

5 -3 7

6 4 -8

Вывод

22

1 1

DL

4.4. Забор (6)

Фермер Питер огородил пастбище забором, состоящим из N досок. Забор имеет форму замкнутой ломаной. Некоторые из этих досок покрашены в белый цвет, а некоторые – нет. Фермер решил покрасить весь забор в белый цвет.

Он обратился в компанию, и ему предложили сделать заказ. Каждый заказ формируется из множества предложений компании. Каждое предложение характеризуется количеством окрашиваемых досок A_i и стоимостью C_i, и заключается в том, что за сумму C_i сотрудники компании покрасят любые A_i идущих подряд досок.

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

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

Ввод. Первая строка входного файла INPUT.TXT содержит два числа: N – число досок (1 ≤ N ≤ 1000) и M – количество возможных предложений компании (1≤ M ≤ 40). Вторая строка содержит n символов, описывающих состояние покраски забора. Символ ‘+’ означает уже окрашенную доску, а символ ‘0’ – неокрашенную. Последующие m строк содержат возможные предложения компании, где каждое предложение описывается двумя натуральными числами A_i и C_i (1≤ A_i ≤ N, 1≤ C_i ≤ 10⁶).

Вывод. В файл OUTPUT.TXT вывести минимальную стоимость покраски забора.

Примеры

Ввод 1 Ввод 2 Ввод 3

1 1 1 1 15 2

0 + 0+000+++0+0+++0

1 10 1 10 2 3

3 5

Вывод 1 Вывод 2 Вывод 3

10 0 13

Комментарий. В последнем примере надо воспользоваться первым предложением для раскраски первой и последней доски (забор замкнутый, поэтому они идут подряд), и дважды вторым предложением, чтобы раскрасить доски с 3 по 5 и с 9 по 11 (10-я доска уже покрашена, но она красится еще раз).