Задача "Роман в томах"

[FoX1488]

Нужно решить эту задачу до завтрашнего обеда.
Кто нибудь, помогите.
Отблагодарю щедро!

[Poma][a]

В голову приходит лишь перебор..

[ViktorR]

Как вариант:
1. Суммируем все страницы и делим на число томов.
Получаем среднее значение числа страниц на том - с округлением до целого.
2. Просматриваем главы по порядку, суммируя страницы - выполняем проверку найденного решения.
Если набрали некоторое число страниц такое, что следующая глава помещяется только на половину или менее (среднее число страниц не превышено), то переходим к формированию следующего тома.
3. Для следующего тома допускаем превышение среднего числа страниц - но только если число непоместившихся страниц следующей главы менее половины.
Так, поочередно, не превышая, а затем превышая среднее число страниц формируем К томов.

Возможно, что алгоритм надо доработать, но я бы как-то так пошел ...

PS: Еще один критерий - среднее число глав в томе. Но это слабый показатель.


Как-то так, ...

[Poma][a]

Угу.. Можно придумать что-то с динамикой.. Решение для i-той главы, это min (решение[i-1], решение[i-2]) + кол-во страниц в i-том.. (Наверное)..

[Аватар]

Простым перебором просто решается, но ACMP.RU отфутболил по времени

А если так:

n - к-во глав
k - к-во томов
S(n,k) - min размер самого большого тома
S(n,1)=A[1]+A[2]+...+A[n]
S(i,i)=max(A[1],A[2],...,A[i])
S(n,k)=min(max(S(n-1,k-1), A[n]),
           max(S(n-2,k-1), A[n-1]+A[n]),
           max(S(n-3,k-1), A[n-2]+A[n-1]+A[n]),
           ...
           max(S(k-1,k-1), A[k]+A[k+1]+...+A[n-1]+A[n]))

Если чего не напутал. Ромахе на засыпку Спать хоца

[Poma][a]

ACMP.RU отфутболил по времени

А можно код?

Ромахе на засыпку

Кстати, очень похоже на правду.. (проверить времени нет)..

[Аватар]

Могу и выложить.
1-ый код перебором - по времени не прошел.
2-ой код все тесты прошел, но длина его не фонтан по сравнению с другими участниками

program Project1;

{$APPTYPE CONSOLE}

var n,i,k: Word;
    a: array [1..100] of Word;

procedure X(d,c,e: Word);
var m,s,t: Word;
begin
  t:=e; s:=0;
  for m:=1 to n-c-k+d do begin
    Inc(s,a[c+m]);
    if s>t then t:=s;
    if d<k then X(d+1,c+m,t)
  end;
  if (d=k) and (i>t) then i:=t
end;

begin
  Reset(input,'input.txt');
  Read(n);
  for i:=1 to n do Read(a[i]);
  Read(k);
  i:=32767;
  X(1,0,0);
  Assign(output,'output.txt');
  Write(i)
end.

program Project1;

{$APPTYPE CONSOLE}

var g,t,i,j,k,u,v,x: Word;
    a,b,d: array[1..100] of Word;

begin
  Reset(input,'input.txt');
  Read(g);
  for i:=1 to g do begin
    Read(a[i]);
    b[i]:=a[i];
    if i>1 then b[i]:=b[i]+b[i-1]
  end;
  Read(t);
  for i:=2 to t do begin
    for j:=i to g do begin
      u:=0;
      x:=65535;
      for k:=1 to j-i+1 do begin
        u:=u+a[j-k+1];
        v:=b[j-k];
        if u>v then v:=u;
        if x>v then x:=v
      end;
      d[j]:=x
    end;
    b:=d
  end;
  Assign(output,'output.txt');
  Write(b[g])
end.

[Poma][a]

Так нечестно!!!
Я лишь просил код перебора А тут.. Эх.. "А задача хорошая, и теперь уже мозги не почистишь, память не сотрешь, свой hard drive в башке не переформатируешь.." (c) TinMan

[Аватар]

Ромаха, у меня там длина кода за 400. Побей их всех, сделай конфетку. Или другой алгоритм

[Poma][a]

Ромаха, у меня там длина кода за 400. Побей их всех, сделай конфетку. Или другой алгоритм

Но время-время-времечко..
И можно шушуть пояснить алгоритм.. я до конца не понимаю..