Кошки и выпуклые фигуры

[soloviewoff]

В воскресном раунде на codeforces.ru была такая задача - http://codeforces.ru/contest/311/problem/B

Несмотря на заковыристое описание, сводится она к следующему:

• Дана последовательность S из m чисел в неубывающем порядке.
• Требуется разбить последовательность на p непрерывных групп [Pis, Pie] с минимизацией суммы sum{i=0,p-1}(sum{j=P[i].s,P[i].e-1}(S[P

Comments

[sleepy_drago]

sweep line segment intersection очень даже нетривиальная штука. в статье они не отрезки пересекают а прямые, что немного проще.

[_winnie]

Не смог распарсить sum{i=0,m-1}(sum{j=Pis,Pie-1}(S[Pie]-S[j])).

Возможно i от 0 до p-1, а не до m-1?
P(i+1)s равно P(i)e, или же P(i)e+1 ?

S[Pie] в сумме по j не меняется? Т.е. можно вынести за знак суммы по j и умножить на (Pie-Pis) ?

Кусочек -S[j] под двумя суммами по i и по j - не суммируется ли случайно в сумму всей последовательности (сумма группы, сумма сумм групп)?

[soloviewoff]

С индексом ошибка была, да. Вот так должно быть более понятно:

sum{i=0,p-1}(sum{j=P[i].s,P[i].e-1}(S[P[i].e]-S[j]))

Да, упростить можно.