Как решить Twisty Movement от Codeforces?

Question

Я читал редакционную статью, но она очень короткая и требует чего-то, что я не понимаю, почему это правда.Почему это эквивалентно нахождению самой длинной подпоследовательности 1*2*1*2* ?.Может кто-нибудь объяснить решение шаг за шагом и обосновать претензии на каждом этапе?http://codeforces.com/contest/934/problem/C

Вот «решение» из редакции, но, как я уже сказал, оно очень короткое и я его не понимаю.Надеюсь, что кто-то может шаг за шагом привести меня к решению, обосновывая требования по пути, а не как в решении здесь.Спасибо.

Начиная с 1 ≤ ai ≤ 2, эквивалентно найти самую длинную подпоследовательность, такую ​​как 1 * 2 * 1 * 2 *.С помощью простого динамического программирования мы можем найти его во O(n) или O(n2) времени.Вы можете увидеть решение O(n2) в модельном решении ниже.Здесь мы вводим подход O (n): поскольку подпоследовательность может быть разбита на 4 части (11...22...11...22...), мы можем установить dp[i][j](i = 1...n, j = 0..3) самой длинной подпоследовательностью a[1...i] с первыми j частями.

Answer 1

Я также думаю, что приведенное объяснение не очень ясно.Вот еще один вариант.

Вы можете свернуть исходный массив

1 1 2 2 2 1 1 2 2 1

в взвешенный массив

2 3 2 2 1
^ ^ ^ ^ ^
1 2 1 2 1

, где числа вверху представляют длины смежных полосповторяющиеся значения в исходном массиве.

Мы можем убедить себя в том, что

1. Оптимальное отражение не «разбивает» никакие смежные последовательности.
2. Оптимальное начало запускаи заканчивается различными значениями (т. е. начинается с 1 и заканчивается 2 или начинается с 2 и заканчивается 1).

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

В частности, мы хотим выполнить переворот таким образом, чтобы некоторая непрерывная монотонная последовательность 112, 122, 211 или 221 имеет максимальный вес.

Один из способов сделать это с помощью динамического программирования - создать 4 вспомогательных массива.

1. A[i]: максимальный вес любого 1 справа от i.
2. B[i]: максимальный вес любого 1 слева от i.
3. C[i]: максимальный вес любого 2 отсправа от i.
4. D[i]: максимальный вес любых 2 слева от i.

Предположим, что если любой из A,B,C,D доступен вне границ,возвращается значение 0.

Мы инициализируем x = 0 и делаем один проход через массив Arr = [1, 2, 1, 2, 1] с весами W = [2, 3, 2, 2, 1].На каждый индекс i у нас есть 2 случая:

1. Arr[i:i+2] == 1 2.В этом случае мы устанавливаем
   • x = max(x, W[i] + W[i+1] + C[i+1], W[i] + W[i+1] + B[i-1]).
2. Arr[i:i+2] == 2 1.В этом случае мы устанавливаем
   • x = max(x, W[i] + W[i+1] + A[i+1], W[i] + W[i+1] + D[i-1]).

Полученный x является нашим ответом.Это решение O (N).