python/TangDou/AcWing/LIS/3549.md

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;
}