Наблюдение, касающееся динамического программирования, которое все, скорее всего, уже давно сделали.

Вместо того чтобы строить массив вида DP[dim_1][dim_2][dim_3]...[dim_N], часто бывает более удобно и понятно строить явным образом граф вида vector <struct {int state_1, state_2, state_3, ..., state_N;} >.

Особенно это удобно и понятно, когда количество измерений больше двух.

Тогда, например, можно не использовать громоздкие конструкции, чтобы инициализировать значения по умолчанию, а просто воспользоваться значениями для полей структуры по умолчанию.

Также это позволяет обойтись вообще без написания циклов в явном виде, всё можно сделать при помощи рекурсивной функции обхода графа.

Таким образом можно добиться даже экономии памяти, если создавать новое состояние непосредственно перед тем, как обход графа собирается пойти в него.

Пример, где такой подход позволил избежать громоздких выкладок с многомерным массивом:

http://acm.timus.ru/problem.aspx?space=1&num=1501 http://ideone.com/tm1TcB

Пост может быть полезен только для div2 .

Вчера я пытался отвечать на вопросы в комментариях к посту о построении массива LCP по суффиксному массиву (алгоритм Касаи). http://codeforces.com/blog/entry/12796

У алгоритма есть определённые тонкости реализации , которые можно понять неправильно, когда вы впервые встречаетесь с ним.

Я попробую развеять все неясности здесь.

Алгоритм в основном цикле рассматривает суффиксы в том порядке, в котором они идут в исходной строке.

Сначала str[0:n], затем str[1:n], затем s[2:n] и так далее.

Если посмотреть на реализацию, то может показаться, что это не так и алгоритм рассматривает суффиксы в порядке сортировки , после прочтения строки j=sa[rank[i] + 1].

На самом деле происходит следующее.

Элемент суффиксного массива под номером X, sa[X], даёт номер Y суффикса в строке str, который идёт в отсортированном списке под номером X .

Так как rank[i] -- это обратная функция к суффиксному массиву, то rank[i] дает такое число Z , что sa[Z] =i, то есть даёт номер i -го суффикса в суффиксном массиве.

Тогда j=sa[rank[i] + 1] -- это позиция в исходной строке, на которой начинается следующий за i -м в порядке сортировки суффикс.

Затем суффиксы тривиальным образом сравниваются за пределами неизвестной части (как в более простых O(n) строковых алгоритмах, таких как префикс — функция или алг-м Манакера).

И полученное значение присваивается не i -му элементу массива lcp , а элементу под номером равным номеру rank[i] i -го суффикса в порядке сортировки, как и "должно быть", потому что LCP показывает длину совпадающей части между двумя соседними суффиксами именно в порядке лексикографической сортировки, а не в порядке их следования в исходной строке.

It is known that working too much is a bad practice. But working not enough is also bad. And also you should work hard to improve, should do things you are not good at. My question is so. How much time it is optimal to practice? How to recreate? Maybe active sport like football is a good choice?