Highway#196

Highway (Розбір)

Пан Бізнесюк мінімізує величину P + K \cdot T, тому зручно одразу перевести весь час у гроші: секунда коштує центів. Тоді проїзд фрагмента безплатною дорогою коштує K \cdot a_i, платною — K \cdot b_i + c_i, а перебудова між дорогами перед фрагментом — K \cdot q_i. Далі мінімізуємо просто суму.

Оскільки на кожному фрагменті є лише два стани (їдемо безплатною чи платною дорогою), напрошується динамічне програмування з двома станами.

Позначимо — мінімальна вартість подолати перші фрагментів так, щоб -й було пройдено безплатною дорогою, і — те саме для платної.

База: \mathrm{dp}[1][0] = K a_1, \mathrm{dp}[1][1] = K b_1 + c_1 (перед першим фрагментом розв'язки немає, почати можна з будь-якої дороги).

Перехід: якщо тип дороги збігається з попереднім, платити за розв'язку не треба, інакше додається K q_i:

\mathrm{dp}[i][0] = K a_i + \min\bigl(\mathrm{dp}[i-1][0],\; \mathrm{dp}[i-1][1] + K q_i\bigr),
\mathrm{dp}[i][1] = K b_i + c_i + \min\bigl(\mathrm{dp}[i-1][1],\; \mathrm{dp}[i-1][0] + K q_i\bigr).

Відповідь — \min(\mathrm{dp}[N][0], \mathrm{dp}[N][1]).

Складність — , що з величезним запасом вкладається в N \le 60.

Головна пастка — розмір чисел: a_i, b_i, c_i сягають 10^{12}, а — до , тому добуток доходить до 2 \cdot 10^{15}, а сума по фрагментах — приблизно до 10^{17}. Це вміщується у 64-бітний тип, але не у 32-бітний. Окремо зверніть увагу на K = 0: тоді час не має значення взагалі й лишається мінімізувати самі дорожні збори.