Codeforces Round 462 (Div. 1) A - A Twisty Movement

2huk · 2023-06-06 21:57:25 · 题解

Codeforces Round 462 (Div. 1) A - A Twisty Movement

题目描述

给定一个由 1 和 2 组成的序列，你可以进行至多一次操作，翻转其中的一个区间内的数。求翻转后的序列的最长非降子序列。

分析

考虑 DP。

由于序列只有两个数，那么最终的非降子序列一定是 \{1, 1, \dots 1, 2, 2, \dots, 2\} 这样的形式。可以这样表示：[1][2]，表示分别由 1 和 2 组成的序列。其中这两个部分可能为空。

如果翻转后得到 [1][2]，那么翻转前的子序列应该是 [1][2][1][2] 的形式，使得交换中间两个子序列后变成非降子序列。同样的，这些序列也可以为空。

因为最多交换一次，所以题目变成了找原序列的最长子序列，且形式为 [1][2][1][2]。

一共有 4 部分，分别将其标号为 0 \sim 3。设状态 f_{i, j}(j \in [0, 3]) 表示序列前 i 个数中，选择前 j 个序列的最长长度。接下来考虑转移。

• 如果第 $i$ 个数为 $1$，那么可以把这个数和以前的拼起来。答案为 $f_{i - 1, 0} + 1$。 否则，如果第 $i$ 个数为 $2$，那么这个数不可以作为第 $0$ 部分。答案为 $f_{i - 1, 0}$。 因此 $f_{i, 0} = \left\{\begin{matrix} f_{i - 1, 0} + 1 & (a_i = 1)\\ f_{i - 1, 0} & (a_i = 2)\end{matrix}\right.$。
• 如果第 $1$ 个部分为空，那么答案为 $f_{i, 0}$。以下都是不空的情况。 如果第 $i$ 个数为 $2$，那么可以把这个数和以前的拼起来。答案为 $f_{i - 1, 1} + 1$。 否则，如果第 $i$ 个数为 $1$，那么这个数不可以作为第 $1$ 部分。答案为 $f_{i - 1, 1}$。 因此 $f_{i, 1} = \left\{\begin{matrix} \max(f_{i, 0}, f_{i - 1, 1} + 1) & (a_i = 2)\\ \max(f_{i, 0}, f_{i - 1, 1}) & (a_i = 1)\end{matrix}\right.$。
• 如果第 $2$ 个部分为空，那么答案为 $f_{i, 1}$。以下都是不空的情况。 如果第 $i$ 个数为 $1$，那么可以把这个数和以前的拼起来。答案为 $f_{i - 1, 2} + 1$。 否则，如果第 $i$ 个数为 $2$，那么这个数不可以作为第 $2$ 部分。答案为 $f_{i - 1, 2}$。 因此 $f_{i, 2} = \left\{\begin{matrix} \max(f_{i, 1}, f_{i - 1, 2} + 1) & (a_i = 1)\\ \max(f_{i, 1}, f_{i - 1, 2}) & (a_i = 2)\end{matrix}\right.$。
• 如果第 $3$ 个部分为空，那么答案为 $f_{i, 2}$。以下都是不空的情况。 如果第 $i$ 个数为 $2$，那么可以把这个数和以前的拼起来。答案为 $f_{i - 1, 3} + 1$。 否则，如果第 $i$ 个数为 $1$，那么这个数不可以作为第 $3$ 部分。答案为 $f_{i - 1, 3}$。 因此 $f_{i, 3} = \left\{\begin{matrix} \max(f_{i, 2}, f_{i - 1, 3} + 1) & (a_i = 2)\\ \max(f_{i, 2}, f_{i - 1, 3}) & (a_i = 1)\end{matrix}\right.$。

最后答案为 f_{n, 3}。

\text{Code}