Сила волшебных заклинаний

Рассмотрим мага на позиции $$$i$$$. Чтобы посчитать сколько единиц урона нанесет $$$i$$$-й маг, нужно знать какими отрезками заклинаний покрывается этот маг. Пусть номер минимального отрезка, который содержит в себе $$$i$$$ равен $$$x$$$, тогда $$$i$$$-й маг нанесет $$$(x - 1) \cdot s_i$$$ единиц урона.

Воспользуемся техникой динамического программирования. Пусть $$$dp[i, msk] = minDamage$$$, $$$i$$$ — позиция мага, которого сейчас рассматриваем, $$$msk$$$ — число в троичной системе счисления, характеризующее отрезки.

Возможные переходы:

  1. Открыть отрезок $$$j$$$: $$$dp[i, msk'] = dp[i, msk], l_j \leq i \leq r_j$$$.
  2. Закрыть отрезок $$$j$$$: $$$dp[i, msk'] = dp[i, msk], l_j + 1 \leq i \leq r_j + 1$$$.
  3. Перейти к следующему магу: $$$dp[i + 1, msk] = dp[i, msk] + cost, cost = s_i$$$ $$$\cdot$$$ индекс минимального открытого отрезка.

Ответ находится в $$$dp[n, msk]$$$, если $$$msk$$$ не содержит открытых отрезков.

Время работы: $$$\mathcal{O}(n \cdot 3^m \cdot m)$$$.