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≤10_6$。
本题读入数据规模较大,需注意优化读入。
C++ 尽量使用 scanf 读入,Java 尽量使用 BufferedReader 读入。
从简化题目出发(求只含12的序列长度)
首先我是考虑的求出该序列的最长非递减子序列
其实只有 $2$ 种状态
- $1111111111…$
– 只可能由 $111111…$ 这种状态转移而来 - $111111112222222222…$
– 可能由 $111111…$ 转移而来
– 也可能由 $111112222…$ 转移而来
代码如下:
#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)2222222…$
– 可以通过 $1111111…$ 转移(仅限于转移到 $111111111111..2$ 这种状态)
– 也可通过 $(11111)2222222…$ 转移 - $(111111122222)11111…$
– 可以通过 $11111111222222…$ 转移(仅限于转移到 $11111112222222..1$ 状态)
– 也可以通过 $(111111122222)11111…$ 转移 - $(111111122222221111111)22222…$
– 可以通过 $(111112222)111…$ 转移(仅限于转移到 $1111222222111111..2$ 状态)
– 也可以通过 $(111111122222221111111)22222…$ 转移
#include <bits/stdc++.h>
using namespace std;
int main() {
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 if (x == 2) {
s2 = max(s1 + 1, s2 + 1);
s4 = max(s3 + 1, s4 + 1);
}
}
cout << max(s3, s4) << endl;
return 0;
}
最后的代码错了,交上去是WA
应该是
已修改,复制的时候忘记改了😂,感谢