Спадок Степана#12

Спадок Степана (Розбір)

Розподільник лише вказує бік, а місце всередині боку визначено однозначно: машина займає найменше вільне. Тому якщо серед перших жителів рівно поїхали ліворуч, то вони зайняли місця 1, 2, \ldots, j, а решта i - j жителів зайняли місця M+1, \ldots, M + (i-j).

Це і є ключ до динамічного програмування: стан повністю описується парою «скільки машин уже приїхало» та «скільки з них поїхало ліворуч».

Нехай \mathrm{dp}[i][j] — максимальний дохід від перших жителів за умови, що з них поїхали ліворуч. Перехід для -го жителя:

  • якщо його спрямувати ліворуч, він займе місце , тому \mathrm{dp}[i][j] = \mathrm{dp}[i-1][j-1] + p_i[j];

  • якщо праворуч, він займе місце M + (i - j), тому \mathrm{dp}[i][j] = \mathrm{dp}[i-1][j] + p_i[M + i - j].

Беремо максимум із двох варіантів. База — \mathrm{dp}[0][0] = 0, решта станів недосяжні (позначаємо «мінус нескінченністю»).

Стан має сенс лише коли j \le M і i - j \le N - M, тобто жоден бік не переповнений; це задає межі циклу по .

Відповідь — \mathrm{dp}[N][M]: усі машин приїхали, і рівно з них стоять ліворуч, бо в кінці стоянка заповнена повністю.

Складність — \mathcal{O}(N^2) за часом і пам'яттю. Доходи додаються, тому накопичуйте суму у 64-бітному типі.