A Twisty Movement
简化题目给定一个有 \(1\)，\(2\) 两个数字组成的数组中，选择一个子串，将 \(1\) 变成 \(2\)，将 \(2\) 变成 \(1\)，求出变化后的序列的最长上升子序列。
思路
简单的情况
如果没有变换操作，题目就变成了一个简单的最长上升子序列问题，答案一定为
\[\]
这种形式，设 \(f\) 表示前 \(i\) 个数中，以 \(1\) 或 \(2\) 这两个数字结尾的最长上升子序列。
转移为
\ = f + (a == 1)\]
\ = \max(f, f + (a == 2))\]
题目转换
再考虑题目中的变换操作，可以知道这次的操作一定会对答案造成一定的变化，要不然这次的转换一定是无用的，不优的，考虑怎么翻转至 \(\) 这种状态。
[*]在 \(\) 这个区间内翻转，有 \(\) 这种情况，\(\) 长度可能为零
[*]在 \(\) 这个区间内翻转，有 \(\) 这种情况，\(\) 长度可能为零
[*]在 \(\) 中间翻转，先将 \(\) 划分成 \(\)，再将中间的 \(\) 翻转成 \(\)，变成了 \(\) 这种情况，其中中间的 \(\) 长度可能为零
由于长度都有可能为零，将这三种情况合并成一种，用 $$$$ 表示，其中每一段都可以为空。
现在就可以 dp 了。
[*]状态：
\(f\) 表示以i为结尾的前 \(j + 1\) 段的最长满足条件的序列长度。
[*]转移：
[*]\(f += (a == 1)\)
[*]\(f = max(f, f + (a == 2))\)
[*]\(f = max(f, f + (a == 1))\)
[*]\(f = max(f, f + (a == 2))\)
[*]答案：
输出 \(f\) 即可。
代码
int main() { for (int i = 1; i > a; scanf("%d", &n); for (int i = 1; i
页:
[1]