\(AcWing\) \(3549\). 最长非递减子序列
一、题目描述
给定一个长度为 \(n\) 的数字序列 \(a_1,a_2,…,a_n\)，序列中只包含数字 \(1\) 和 \(2\)。
现在，你要选取一个区间 \([l,r](1≤l≤r≤n)\)，将 \(a_l,a_{l+1},…,a_r\) 进行翻转，并且使得到的新数字序列 \(a\) 的最长非递减子序列的长度尽可能长。
请问，这个最大可能长度是多少？
一个非递减子序列是指一个索引为 \(p_1,p_2,…,p_k\)的序列，满足 \(p_1<p_2<…<p_k\) 并且 \(a_{p1}≤a_{p2}≤…≤a_{pk}\)，其长度为 \(k\)。
输入格式
第一行一个整数 \(n\)。
第二行 \(n\)个空格隔开的数字 \(1\) 或 \(2\)，表示 \(a_1,…,a_n\)。
输出格式
输出一个整数，表示得到的新数字序列 \(a\) 的最长非递减子序列的最大可能长度。
数据范围
对于 \(30\%\) 的数据，\(1≤n≤100\)。
对于 \(100\%\) 的数据，\(1≤n≤106\)。
本题读入数据规模较大，需注意优化读入。
\(C++\) 尽量使用 \(scanf\) 读入，\(Java\) 尽量使用 \(BufferedReader\) 读入。
输入样例\(1\)：
4
1 2 1 2
输出样例1：
4
输入样例2：
10
1 1 2 2 2 1 1 2 2 1
输出样例2：
9
二、从简化题目出发（求只含12的序列长度）
首先我是考虑的求出该序列的最长非递减子序列
其实只有 \(2\) 种状态
-
\(1111111\)…
只可能由 \(111111\)… 这种状态转移而来 -
\(111111112222222222\)…
可能由 \(11111111\)… 转移而来
也可能由 \(111112222\)… 转移而来
\(Code\)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int s1 = 0, s2 = 0;
while (n--) {
int x;
cin >> x;
if (x == 1) {
s1++; // 如果当前数字是 1，则状态1的长度加1
} else {
s2 = max(s1 + 1, s2 + 1); // 如果当前数字为2，可能由两种状态转移而来
}
}
cout << max(s1, s2) << endl;
return 0;
}
三、回归题目（包括反转）
对于本题目而言，比上述的简单模型多加了一个条件：可以进行反转操作。
这就意味着，我们可以求一个形如：\(111111222222111111222222\)的子序列，然后进行反转操作让其变成 \(1111111112222222\)…的子序列
现在我们开始枚举状态：
-
\(1111111\)....
只能通过 \(111111\)…转移 -
\((111111)2…\)
可以通过 \(1111111\)… 转移（仅限于转移到 \(111111111111..2\) 这种状态）
也可通过 \((11111)2222222\)…转移 -
\((111111122222)11111\)…
可以通过 \(11111111222222\)… 转移（仅限于转移到 \(11111112222222..1\) 状态）
也可以通过 \((111111122222)11111\)…转移 -
\((111111122222221111111)22222\)…
- 可以通过 \((111112222)111\)… 转移（仅限于转移到 \(1111222222111111..2\) 状态）
- 也可以通过 \((111111122222221111111)22222\)… 转移
\(Code\)
#include <bits/stdc++.h>
using namespace std;
int main() {
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
if (x == 1) {
s1++;
s3 = max(s2 + 1, s3 + 1);
} else {
s2 = max(s1 + 1, s2 + 1);
s4 = max(s3 + 1, s4 + 1);
}
}
cout << max({s1, s2, s3, s4}) << endl;
return 0;
}