024. Роман в томах

(Время - 1 сек., память - 16 Мб)

В романе N глав. В i-той главе ai страниц. Требуется издать роман в K томах так, чтобы объем самого «толстого» тома был минимален. В каждом томе главы располагаются по порядку своих номеров.

Требуется написать программу, которая найдет количество страниц в самом «толстом» томе.

Входные данные

В первой строке входного файла input.txt записано число N (1 ≤ N ≤ 100). Во второй строке через пробел записаны N чисел – количество страниц в каждой главе. Количество страниц в романе не превышает 32767. В третьей строке записано число K (1 ≤ K ≤ N).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести количество страниц в самом «толстом» томе.

Примеры

input.txt

output.txt

1

3
1 2 1
2

3

2

4
1 2 1 1
3

2

Разбор

Задача решается методом динамического программирования. Обозначим через B(i, j) – количество страниц в самом «толстом» томе из i глав, если их издавать в j томах по требуемому в условии задачи условию. Получим рекуррентные соотношения на эту величину. Если j=1, то . Для издания романа в j+1 томе в последний том могут попасть главы: либо i (ai страниц), либо i-1 и i (ai-1 и ai страниц), …, либо j+1, j+2, …, i ( страниц). Для каждого из этих способов размещения глав в j+1 томе величина B для j томов уже вычислена. Берем максимум из этих величин и находим минимум из всех способов.

Программа на Паскале

var

  a, b, c : array [1..100] of integer;

  n, k, i, j, s, min, l, t : integer;

function max(a,b:integer):integer;

begin

  if a>b then max:=a else max:=b

end;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n);

  for i:=1 to n do read(a[i]);

  read(k);

  s:=a[1]; b[1]:=a[1];

  for i:=2 to n do

  begin s:=s+a[i]; b[i]:=s end;

  for j:=2 to k do

  begin

    for i:=j to n do

    begin

      min:=maxint; s:=0;

      for l:=1 to i-j+1 do

      begin

        s:=s+a[i-l+1];

        t:=max(s,b[i-l]);

        if t<min then min:=t

      end;

      c[i]:=min

    end;

    b:=c

  end;

  write(b[n])

end.

Программа на С

 

Информация о задаче

Автор, источник

Волченков С.Г. и др. Ярославские олимпиады по информатике. – М.: БИНОМ. Лаборатория знаний, 2010

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 5-й тур

Тематика

Динамическое программирование

Примерная сложность

41%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=523

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 24.05.2012