algorithm - 如何解决 Codeforces 的 Twisty Movement？

Question

我读过这篇社论，但它很短，并且声称我不明白为什么它是真的。为什么等同于求1*2*1*2*的最长子序列？有人可以逐步解释解决方案并在每一步证明 claim 的合理性吗？ http://codeforces.com/contest/934/problem/C

这是社论中的“解决方案”，但正如我所说，它非常简短，我不明白。希望有人能指导我一步一步地解决这个问题，而不是像这里的解决方案那样。谢谢。

Since 1 ≤ ai ≤ 2, it's equivalent to find a longest subsequence like 1 * 2 * 1 * 2 * . By an easy dynamic programming we can find it in O(n) or O(n2) time. You can see O(n2) solution in the model solution below. Here we introduce an O(n) approach: Since the subsequence can be split into 4 parts (11...22...11...22...) , we can set dp[i][j](i = 1...n, j = 0..3) be the longest subsequence of a[1...i] with first j parts.

Answer 1

我还认为引用的解释不是很清楚。这是另一个镜头。

你可以折叠一个原始数组

1 1 2 2 2 1 1 2 2 1

放入加权数组

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

其中顶部的数字表示原始数组中重复值的连续 strip 的长度。

我们可以说服自己

1. 最佳翻转不会“打断”任何连续序列。
2. 最佳翻转以不同的值开始和结束(即以 1 开始以 2 结束，或以 2 开始以 1 结束)。

因此，加权数组包含足够的信息来解决问题。我们想要翻转加权数组 s.t. 的连续切片。与一些连续的单调序列相关联的权重之和被最大化。

具体来说，我们希望以某种连续的单调序列 112、122、211 或 的方式执行翻转221 具有最大权重。

使用动态规划实现此目的的一种方法是创建 4 个辅助数组。

1. A[i] : i 右边任意 1 的最大权重。
2. B[i] : i 左边任意 1 的最大权重。
3. C[i] : i 右边任意 2 的最大权重。
4. D[i] : i 左边任意 2 的最大权重。

假设如果越界访问 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) 的解决方案。