当前位置：首页 > news >正文

A Twisty Movement

news 2026/3/26 17:15:07

CF933A A Twisty Movement

简化题目

给定一个有 $1$，$2$ 两个数字组成的数组中，选择一个子串，将 $1$ 变成 $2$，将 $2$ 变成 $1$，求出变化后的序列的最长上升子序列。

思路

简单的情况

如果没有变换操作，题目就变成了一个简单的最长上升子序列问题，答案一定为

\[[1...1][2...2] \]

这种形式，设 $f[i][1/2]$ 表示前 $i$ 个数中，以 $1$ 或 $2$ 这两个数字结尾的最长上升子序列。

转移为

\[f[i][1] = f[i-1][1] + (a[i] == 1) \]

\[f[i][2] = \max(f[i][1], f[i-1][2] + (a[i] == 2)) \]

题目转换

再考虑题目中的变换操作，可以知道这次的操作一定会对答案造成一定的变化，要不然这次的转换一定是无用的，不优的，考虑怎么翻转至 $[1...1][2...2]$ 这种状态。

在 $[1...1]$ 这个区间内翻转，有 $[2...2][1...1][2...2]$ 这种情况，$[1...1]$ 长度可能为零
在 $[2...2]$ 这个区间内翻转，有 $[1...1][2...2][1...1]$ 这种情况，$[2...2]$ 长度可能为零
在 $[1...1][2...2]$ 中间翻转，先将 $[1...1][2...2]$ 划分成 $[1...1][1...1][2...2][2...2]$，再将中间的 $[1...1][2...2]$ 翻转成 $[2...2][1...1]$，变成了 $[1...1][2...2][1...1][2...2]$ 这种情况，其中中间的 $[2...2][1...1]$ 长度可能为零

由于长度都有可能为零，将这三种情况合并成一种，用 $$[1...1][2...2][1...1][2...2]$$ 表示，其中每一段都可以为空。

现在就可以 dp 了。

状态：
$f[i][j]$ 表示以i为结尾的前 $j + 1$ 段的最长满足条件的序列长度。
转移：

$f[i][0] += (a[i] == 1)$
$f[i][1] = max(f[i][0], f[i-1][1] + (a[i] == 2))$
$f[i][1] = max(f[i][1], f[i-1][2] + (a[i] == 1))$
$f[i][1] = max(f[i][2], f[i-1][3] + (a[i] == 2))$

答案：
输出 $f[n][4]$ 即可。

代码

int main() {for (int i = 1; i <= n; i++) cin >> a[i];scanf("%d", &n);for (int i = 1; i <= n; i++) {int a; scanf("%d", &a);f[i][0] = f[i - 1][0] + (a == 1);f[i][1] = max(f[i][0], f[i-1][1] + (a == 2));f[i][2] = max(f[i][1], f[i-1][2] + (a == 1));f[i][3] = max(f[i][2], f[i-1][3] + (a == 2));}int ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, f[i][3]);printf("%d\n", ans);return 0;
}