Оптимизация Кнута: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Пусть мы хотели посчитать $dp_{i, j} = \max_{k=1}^i f(i, j, k}$, которая удовлетворяла [монотонность точ...») |
KiKoS (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
Пусть мы хотели посчитать $dp_{i, j} = \max_{k=1}^i f(i, j, k}$, которая удовлетворяла [монотонность точки перегиба|монотонности точки перегиба]] сразу по двум параметрам (иначе говоря, для нее $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$. Тогда можно перебирать параметры пересчета динамики в таком порядке, чтобы для пары $\{i, j\}$ уже были известны $opt_{i - 1, j}, opt_{i, j + 1}$. Если пересчитывать динамику, используя это приближение, то суммарное количество операций будет $O(n^2)$. Действительно, для всех $i, j : j - i = const$ мы суммарно рассмотрим $O(n)$ точек перегиба, а разных значений этой функции бывает $O(n)$. | Пусть мы хотели посчитать $dp_{i, j} = \max_{k=1}^i f(i, j, k}$, которая удовлетворяла [монотонность точки перегиба|монотонности точки перегиба]] сразу по двум параметрам (иначе говоря, для нее $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$. Тогда можно перебирать параметры пересчета динамики в таком порядке, чтобы для пары $\{i, j\}$ уже были известны $opt_{i - 1, j}, opt_{i, j + 1}$. Если пересчитывать динамику, используя это приближение, то суммарное количество операций будет $O(n^2)$. Действительно, для всех $i, j : j - i = const$ мы суммарно рассмотрим $O(n)$ точек перегиба, а разных значений этой функции бывает $O(n)$. | ||
− | <syntaxhighlight lang='c++' line='line> | + | <syntaxhighlight lang='c++' line='line'> |
for (int i = 1; i <= n; i++) { | for (int i = 1; i <= n; i++) { | ||
for (int j = m; j >= 1; j--) { | for (int j = m; j >= 1; j--) { |
Версия 12:50, 27 сентября 2019
Пусть мы хотели посчитать $dp_{i, j} = \max_{k=1}^i f(i, j, k}$, которая удовлетворяла [монотонность точки перегиба|монотонности точки перегиба]] сразу по двум параметрам (иначе говоря, для нее $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$. Тогда можно перебирать параметры пересчета динамики в таком порядке, чтобы для пары $\{i, j\}$ уже были известны $opt_{i - 1, j}, opt_{i, j + 1}$. Если пересчитывать динамику, используя это приближение, то суммарное количество операций будет $O(n^2)$. Действительно, для всех $i, j : j - i = const$ мы суммарно рассмотрим $O(n)$ точек перегиба, а разных значений этой функции бывает $O(n)$.
<syntaxhighlight lang='c++' line='line'> for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) { for (int k = opt[i-1][j]; k <= opt[i][j+1]; k++) { int val = cost(i, j, k); if (val < f[i][j]) f[i][j] = val, opt[i][j] = k; } }
} </syntaxhihlight>
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s