Вправи Степана#81

Вправи Степана (Розбір)

Чому працює проста динаміка. Здавалося б, стан має включати рівень сили — адже вправу не можна вивчити, якщо сили менше за K_i. Але зверніть увагу: сила ніде не «витрачається» пропорційно й не впливає на величину приросту. Вона потрібна лише для того, щоб подолати поріг K_i. Отже більша сила ніколи не гірша, і достатньо для кожного дня зберігати максимально можливий рівень:

\mathrm{dp}[i] = \text{найбільша сила, з якою можна підійти до початку дня } i .

Скільки разів робити вправу. Оскільки F_i > 0, приріст F_i \cdot X зростає разом із — отже завжди вигідно робити якнайбільше у межах обраного режиму. Режимів рівно два:

  • без утоми: X = \min(B_i, T), наступний доступний день — i+1. Можливо, лише якщо A_i \le \min(B_i, T);

  • на межі: X = B_i, але тоді днів відпочинку, наступний доступний день — i + 1 + D. Має сенс лише якщо B_i > T.

Проміжні значення перебирати не треба — вони дають менший приріст за тієї самої ціни. Це і робить розв'язок лінійним замість перебору по 10^6 повторень.

Переходи.

\mathrm{dp}[i+1] \leftarrow \mathrm{dp}[i] \quad (\text{відпочинок}),

а якщо \mathrm{dp}[i] \ge K_i — ще й

\mathrm{dp}[i+1] \leftarrow \mathrm{dp}[i] + F_i \cdot \min(B_i, T) - K_i, \qquad \mathrm{dp}[i+1+D] \leftarrow \mathrm{dp}[i] + F_i \cdot B_i - K_i .

Індекси, що вилітають за , зводимо до «кінець серії»: за умовою, якщо перевтома трапилась в останні дні, відпочинок просто триває після завершення курсу й нічого не змінює. Початкове значення — \mathrm{dp}[1] = 0.

Відновлення відповіді. Разом із зберігаємо, з якого дня стався перехід і скільки разів там виконувалася вправа. Наприкінці йдемо назад від «кінця серії», заповнюючи масив X_i; усі дні, які не трапилися на цьому шляху, лишаються нулями — це і дні відпочинку, і дні, «з'їдені» перевтомою.

Складність — . Сила сягає 10^5 \cdot 10^6 \cdot 10^6, тож обов'язково -бітний тип, а виведення чисел краще робити одним буфером.