\Section{Динамика (продолжение)}{19 октября}{Анастасия Софронова}

\Subsection{Умножение матриц}

\Subsubsection{Собственно, умножение}

Если есть 2 матрицы $A$ и $B$ размеров $(n, m)$ и $(m, k)$ соответственно (количество столбцов в первой обязательно равно количеству строк во второй), то мы умеем умножать их за $nmk$. Эта операция ассоциативна. Больше про умножение матриц мы ничего пока знать не должны.

\Subsubsection{Постановка задачи}

Есть $n$ матриц $A_1, A_2, \ldots , A_n$, $size(A_i) = (m_i, m_{i + 1})$. Перемножить их за минимальное количество операций.

\Subsubsection{Решение}

Суть задачи --- оптимально расставить скобки. Это динамика по подотрезкам. Давайте переберём, какую операцию совершить последней. Пусть мы считаем ответ на отрезке $[L, R]$. Пусть мы выбрали знак умножения между матрицами $A_M$ и $A_{M + 1}$. После того, как мы полностью перемножим все матрицы на отрезках $[L, M]$ и $[M + 1, R]$, у нас слева останется матрица размерностей $(m_L, m_{M + 1})$, а справа --- $(m_{M + 1}, m_R)$. Их мы перемножим за $m_L \cdot m_{M + 1} \cdot m_R$. Итак, ответ для отрезка --- оптимум из значений \t{$dp[L][M] + dp[M + 1][R] + m_L \cdot m_{M + 1} \cdot m_R$}. База: \t{$dp[L][L] = 0$}.

\Subsection{Арифметические выражения}

\Subsubsection{Постановка задачи}

Дано арифметическое выражение, в котором присутствуют только знаки $+$ и $\cdot$, необходимо максимизировать результат. Для простоты: все числа натуральные.

\Subsubsection{Решение}

Точно такая же динамика по подотрезкам. Перебираем последнюю операцию, которая разбивает наш отрезок на 2. Берём максимальный ответ на левом отрезке и на правом, применяем к ним нашу последнюю операцию. Из всех таких переходов выбираем максимум. $Time = \Theta (n^3)$

\Subsection{Задача о погрузке грузов}

\Subsubsection{Постановка задачи}

Есть бесконечное количество кораблей. У каждого корабля одна и та же грузоподъёмность $W$. Есть последовательность из $n$ грузов, у каждого есть вес $a_i$. Мы можем брать какой-то префикс последовательности и какой-то суффикс и грузить эти грузы на корабль. При этом сумма весов грузов на корабле не должна превышать $W$. Необходимо погрузить все грузы на минимальное количество кораблей.

\Subsubsection{$O(n^4)$}

\t{$dp[L][R]$} --- минимальное количество кораблей, на которые мы можем погрузить все грузы с $L$ по $R$.
Перебираем, какой префикс и какой суффикс мы погрузим на следующий корабль. У нас $O(n^2)$ состояний и $O(n^2)$ переходов --- за линию перебираем префикс, заканчивающийся в позиции $i$ и за линию суффикс, начинающийся в $j$. Из $[L, R]$ переходим в $[i, j]$.

\Subsubsection{$O(n^3)$}

Заметим, что нам не нужно перебирать и префикс, и суффикс, так как невыгодно грузить корабль не до конца. Итак, для фиксированного $i$ мы берём такое $j$, чтобы поместить на корабль как можно больше грузов. Заметим, что при увеличении индекса $i$ такой индекс $j$ также увеличивается, т.е. мы можем применить метод двух указателей.

\Subsubsection{$O(n^2)$, измельчение переходов}

А в чём, собственно, была проблема? В том, что каждый раз мы пытались загрузить корабль полностью. Давайте за один переход грузить всего один груз. Параметры отстанутся такими же --- границы текущего отрезка. Но в динамике мы будем минимизировать пары: сколько кораблей уже отправлено и какой вес погружен на последний.
Для начала рассмотрим переходы. Из состояния, где отправлено $k$ кораблей, на неотправленный погружен вес $w$, а от грузов остался отрезок $[L, R]$, мы можем сделать 3 вещи. Первое: отправить корабль. Тогда $k$ перейдёт в $k + 1$, а $w$ в $0$. Мы можем погрузить левый груз, тогда $w$ перейдёт в $w + a_L$, $L$ в $L + 1$; или правый, тогда $w$ перейдёт в $w + a_R$, а $R$ в $R - 1$. Итак, у нас не $n$ переходов, а всего 3. Правда, один из них делается в тот же отрезок, и это не очень приятно. Как бороться с переходом в себя? Можно сделать не 3, а 4 перехода. В одном из них мы грузим левый груз, не отправляя при этом корабль, в другом, напротив, отправляем; так же с правым грузом.
Замечательно то, что мы можем получить ответ с $O(n)$ памяти, храня только последнюю строчку матрицы, где считаем динамику. Для этого $L$ нужно перебирать в порядке возрастания, а $R$ в порядке убывания, тогда всё будет считаться корректно и в нужном порядке.

\Subsubsection{Так почему же это работает?}

Почему мы можем минимизировать пары? Давайте рассмотрим пары $(k_1, w_1)$ и $(k_2, w_2)$.
Есть 2 очевидных случая. Пусть $k_1 = k_2$, $w_1 \neq w_2$. Здесь мы обращаем внимание только на одно значение и, естественно, пытаемся его минимизировать.
Пусть теперь $k_1 < k_2$, $w_1 \leq w_2$. Здесь минимизация обоих значений также вопросов не вызывает.
Теперь пусть $k_1 < k_2$, $w_1 > w_2$. Заметим, что из $(k_1, w_1)$ мы можем перейти в $(k_1 + 1, 0)$ и $k_1 + 1 \leq k_2$, $0 \leq w_2$, значит, это состояние ничем не хуже $(k_2, w_2)$.
Итак, мы можем минимизировать пары, динамика работает.