Alexander: Этот пример - примерно 4-й курс мехмата (моя дочка сейчас готовится к экзамену - там очень похожая тематика). Конечно, просто понять формулы и приёмы можно и в 11 классе, но чтобы они вошли в общую картину мира, надо знать гораздо больше.
volyihin: В знаке закодировано направление, с которого мы пришли в клетку (a,b): если в ней +x, то пришли с клетки (a-x,b) - и элемент x принадлежит первому множеству, а если -x - то пришли с (a,b-x), и элемент x принадлежит второму множеству.
Вики утверждает, что достаточно O(n*m^2) памяти, где m - наибольшее число, а n - длина последовательности. Это заметно меньше, чем O(S^2). Интересно, как.
Владимир Петриго: Да, если на обратном пути проверять именно возможность прохода по последнему элементу, то не заблудимся. Будет ли проще решение? Возможно, будет. Хотя и незначительно.
А если последовательность содержит меньше 40 элементов, то можно сделать наоборот - завести массив UInt64[S/3+1,S/3+1], и сразу накапливать в его посещённых элементах разбиение на подмножества - в троичной системе. Тогда идти назад не придётся, в последней клетке будет сразу готов ответ.
Японский Городовой: Действительно, там же "текущее положение планет"! Большие планеты у нас движутся по окружности, а далёкие карликовые за время существования программы сдвинутся так мало, что этим можно пренебречь, достаточно оставить их в положении на какой-нибудь 2020 год.
Ашот Такиев: Если получится восстановить, то хорошо. Но всё зависит от того, что именно вы храните в массиве. Если это, допустим, история заполнения достижимых ячеек (sum(S1),sum(S2)), то при обратном поиске есть опасность пойти по ложному пути.
Массив обратных ссылок - самый дешёвый и надёжный вариант. И его можно делать не дополнительным, а единственным (ссылки нет - клетка пока недостижима).
Ашот Такиев: В начале d={-1,-1,-1,...} - ни одной последовательности у нас нет.
Приходит элемент с индексом 0, равный 1. Он образует последовательность длины 1, предыдущего элемента у него нет. Поэтому у нас есть последовательность длины 1, кончающаяся на элементе с индексом 0 (d[1]=0), и prev[0]=-1.
Приходит элемент с индексом 1, равный 2. Последовательность длины 1 из него делать неэффективно (поскольку у нас уже есть последовательность с меньшим последним элементом), но мы можем добавить его к имеющейся последовательности, и получить последовательность длины 2: d[2]=1, prev[1]=0 (элемент с индексом 1 идёт после элемента с индексом 0).
Аналогично обрабатываем 7,8 и 9: d[3]=2, prev[2]=1; d[4]=3, prev[3]=2; d[5]=4,prev[4]=3.
Приходит 5 (элемент с индексом 5). Его мы можем вставить после двойки, получив лучшую последовательность длины 3: d[3]=5, prev[5]=1. Дальше получится d[4]=6, prev[6]=5 и d[3]=7, prev[7]=1.
Чтобы построить по массивам d и prev ответ, надо ещё поработать. Начать с элемента d[5]=4 (самая длинная последовательность), потом взять prev[4]=3, prev[3]=2, prev[2]=1, prev[1]=0, prev[0]=-1. Это (кроме последнего числа) индексы ответа, записанные в обратном порядке. Берём элементы исходного массива по этим индексам: 1,2,3,8,9 - они и дадут ответ.
Похоже, что без Find1 можно обойтись, вызвав сразу Find2(0,n-1,0,n-1).
Фактически, мы здесь проверяем некоторое свойство для двух отрезков, для чего делим один из отрезков пополам, и сопоставляем каждую половину с другим отрезком. Может быть, задача не очень удачна, но этот приём надо знать. Например, это решение легко обобщается на двумерный случай (найти два таких числа в массиве, монотонном по обеим координатам). С указателями вы там намучаетесь.
ifqthenp: Удачи. Конечно, рекурсия в сочетании с побочными эффектами может озадачить проверяющего. Но здесь такой подход делает код и проще, и эффективнее.
ifqthenp: Да, рекурсия здесь слегка не по делу, задача проще без неё (в обоих случаях). Для второй достаточно отсортировать массив и свести задачу к первой (O(n*log n)). Вот если массив портить нельзя, а дополнительная память разрешается не более O(log(n)) - тут надо думать.
стоимость парника - 3 дополнительных клетки.
Идём снизу. Конфигурацию будем задавать отрезками пересечения линии с парниками. Например, [1,2],[3] - линия пересекла два парника, один занял первые две клетки, другой - третью.
В начале у нас парников нет, штраф нулевой.
В первой строке мы можем построить такие конфигурации:
(A1): [1,2],[3] - штраф=9 (два парника и 3 клетки)
(A2): [1,2,3] - штраф=6
(A3): [2],[3] - штраф=8
(A4): [2,3] - штраф=5.
В следующей строке возможны конфигурации
(B1): [1],[2],[3] - штраф=14 (из A3)
(B2): [1],[3] - штраф=13 (из A3 или А4)
(B3): [1,2],[3] - штраф=12 (из A1)
(B4): [1],[2,3] - штраф=11 (из A4)
(B5): [1,2,3] - штраф=9 (из A2)
B1 может получиться только из A3 (продлили парник [2]), остальные конфигурации - из любой другой.
Строка 3:
(C1): [1],[2],[3] - штраф=17 (из B1)
(C2): [1],[2] - штраф=16 (из B1 или B4)
(C3): [1],[2,3] - штраф=14 (из B4)
(C4): [1,2],[3] - штраф=15 (из B3)
(C5): [1,2] - штраф=14 (из B3 или B5)
(C6): [1,2,3] - штраф=12 (из B5)
Последняя строка:
(D1): [1],[2],[3] - штраф=20 (из C1)
(D2): [1],[2] - штраф=18 (из C2)
(D3): [1],[2,3] - штраф=17 (из C3)
(D4): [1,2],[3] - штраф=18 (из C4)
(D5): [1,2] - штраф=16 (из C5)
(D6): [1,2,3] - штраф=15 (из C6)
(D7): [1] - штраф=15 (из C3)
(D8): [1],[3] - штраф=19 (из С1 или С3).
Таким образом, получаем две оптимальных конфигурации: либо один парник на всю площадь, либо два парника - один в левом ряду, другой в двух правых.
Strollager: Для плоскости z=0 - да. В этом случае x'=x, y'=y. Если бы вы проектировали на плоскость x+y+z=1, можно было бы взять О=(0,0,1), X=(1,-1,0)/sqrt(2), Y=(1,1,-2)/sqrt(6), и формулы для x', y' были бы сложнее.
А что это за компилятор? С 16-битным int и действующим long double? Неужели Borland?
И до какого числа надо считать факториал? Переход к каждому новому типу (short - long - double - int64) увеличит порог примерно на 3-5 чисел, так что в общем случае потребуется длинная арифметика.
