Sanrd(sanrd)

Sanrd(sanrd)

【题目描述】
小A 有一个长度为n 的序列a,满足a 中的所有元素都是1 或2。
你想要篡改这个序列。你可以任意选择原序列的一段区间[l; r],并将al; al+1; …… ; ar
翻转。为了不被发现,你只能执行该操作至多一次。
你希望最大化操作之后序列最长不下降子序列的长度,请求出这个值。
序列a 的一个不下降子序列是一个下标序列p1; p2; : : : ; pk,满足p1 < p2 < : : : < pk
且ap1<= ap2……<= apk。定义它的长度为k。
【输入格式】
从文件sanrd.in 中读入数据。
第一行一个整数n,表示序列的长度。
第二行n 个用空格隔开的正整数,描述了序列a。
【输出格式】
输出到文件sanrd.out 中。
输出一行一个整数,表示操作之后序列最长不下降子序列长度的最大值。
【样例1 输入】
4
1 2 1 2
【样例1 输出】
4
【样例2 输入】
10
1 1 2 2 2 1 1 2 2 1
【样例2 输出】
9
【样例2 解释】
你可以选择区间[3; 7] 并将其翻转,得到的序列为[1; 1; 1; 1; 2; 2; 2; 2; 2; 1],它
的最长不下降子序列的长度为9。不难发现对于这组数据不存在更优的解。
【子任务】
对于60% 的数据,n <= 200;
对于90% 的数据,n<= 2000;
对于100% 的数据,1<= n<=2 * 10^5; 1 <=ai <=2。

信息

难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者