Skyscraper#254

Skyscraper (Editorial)

Автор задачі:	Антон Ципко
Задачу підготував:	Марко Гришечкін
Розбір написали:	Марко Гришечкін та Антон Ципко

Блоки 1-3

Відсортуємо хмарочоси у порядку зростання (незростання) краси поверхів. Будемо розв'язувати задачу за допомогою динамічного програмування. Нехай $d p_{i}$ dp_i — максимальна можлива сума, якщо розглядати лише перші $i$ хмарочоси. Тоді

d p_{i} = j < i max (d p_{j} + (a_{i} - a_{j}) \cdot b_{i})

dp_i = \max_{j<i} (dp_j + (a_i - a_j) \cdot b_i)

Відповідь буде у $d p_{n}$ dp_n.

Блок 4

Відсортуємо хмарочоси у порядку зростання (незростання) краси поверхів. Якщо побудувати хмарочоси саме в такому порядку, то сумарна краса поверхів буде максимально можливою.

/textbfДоведення: нехай $m$ "— максимальна висота серед усіх хмарочосів. Для будь-якої висоти від $1$ до $m$ з хмарочоса Вуса на такій висоті буде видно рівно один поверх одного з $n$ хмарочосів. Доведемо, що при такому порядку хмарочосів, для довільної висоти $i$ , з хмарочоса Вуса буде видно поверх з максимальною красою. Цей поверх належить першому зліва хмарочосу з висотою більшою або рівною $i$ . Через те, що ми відсортували хмарочоси за красою, то цей хмарочос має найбільшу красу серед усіх хмарочосів з висотою більшою або рівною $i$ .

d p_{i}

d p_{i} = j < i max (d p_{j} + (a_{i} - a_{j}) \cdot b_{i})

d p_{n}