单调序列 题解【构造】【DP】【找规律（雾】

点击量：190

    考试读错题了导致没有\(\text{AK}\)。

目录

题目描述

\(\text{GISPZJZ}\)有一个长度为\(n\)的序列\(a_1,a_2,\dots ,a_n\)。序列的所有元素都是\(1\)或者\(2\)。我们称一序列是该序列的不下降子序列\(p_1,p_2,\dots ,p_k\)，满足\(1\le p_1<p_2<p_3<\dots <p_k\le n\)，且\(a_{p_1}\le a_{p_2}\le \dots \le a_{p_n}。

现在\(\text{GISPZJZ}\)可以选择序列中的一段区间\([L,R]\)，然后将整段反转，例如挑选区间\([2,4]\),可以将序列\(\{a_1,a_2,a_3,a_4,a_5\}\)变换为\(\{a_1,a_4,a_3,a_2,a_5\}\)。 在此基础上，\(\text{GISPZJZ}\)希望在反转后，序列的最长不下降子序列最长。当然，\(\text{GISPZJZ}\)也可以选择不反转任何区间。现在要求求出最优情况下，序列的最长不下降子序列的长度。

输入输出格式

输入：

第一行一个正整数\(n\)。

第二行\(n\)个数，分别为\(a_1,a_2,\dots ,a_n\)，满足\(1\le a_i\le 2\)。

输出：

一行一个正整数\(x\)，表示答案。

输入输出样例

样例输入：

6
1 2 2 1 2 1

样例输出：

5

样例说明：

选择区间为\([2,4]\)，翻转后的序列为\(\{1,1,2,2,2,1\}\)，最长不下降子序列为\(a_1,a_2,a_3,a_4,a_5\)，长度为\(5\)。

数据范围与约定

对于\(10\%\)的数据，\(1\le n\le 10\)。
对于\(40\%\)的数据，\(1\le n\le 200\)。
对于\(70\%\)的数据，\(1\le n\le 2000\)。
对于\(100\%\)的数据，\(1\le n\le 100000\)。

题解：

    这个题不要把子序列看成子串了。

    我们知道这个题中\(\text{LIS}\)的结构一定是\(\{1,1,1,\dots ,2,2,2\}\)或者\(\{1,1,\dots ,1,1\},\{2,2,\dots ,2,2\}\)，因此我们翻转一个区间如果做出贡献，那么这个区间在\(\text{LIS}\)中一定是\(\{1,\dots ,2\}\)，也就是说，假设我们翻转的区间是\([L,R]\)，那么\([1,L)\)在\(\text{LIS}\)中一定全是\(1\)；\((R,n]\)在\(\text{LIS}\)中一定全是\(2\)。那么对\([L,R]\)之间就是前面一部分由\(1\)做贡献，后面一部分由\(2\)做贡献。

    这一引理可以反证，如果\([L,R]\)在\(\text{LIS}\)中全部是\(1\)，那么翻转后不会对原\(\text{LIS}\)造成任何变化，因为区间中的\(1\)还是那么多，\(2\)的情况同理。

    那么我们翻转一个区间就是让它变成“前面一段由\(2\)做贡献，后面一段由\(1\)做贡献”。如果我们把它转化回\(\text{LIS}\)问题，那么就要让\(1\)的优先级临时不小于\(2\)，但是后面还是要小于的，可以想到把\([L,R]\)之间的\(1\)变成\(3\)，最后一段\(2\)就是\(4\)了。此时整个\(\text{LIS}\)就形如\(\{1,\dots ,1,2,\dots 2,3\dots 3,4\dots 4\}\)，其中可以有元素不出现。然后\(\{2,3\}\)段就是我们要翻转的区间了。

    这一构造思路是为了保证只翻转一次，临时使\(1\)的优先级高于\(2\)且仅有一次，是一种非常不错的想法。

    然后我们求\(\text{LIS}\)时用\(f[i](i\in[1,4])\)表示以元素\(i\)结尾的\(\text{LIS}\)长度，如果\(a_i=1\)，那么它可以作为\(1\)接在\(f[1]\)的后面，也可以作为\(3\)接在\(f[2],f[3]\)的后面（不接在\(f[1]\)后面是因为\(f[3]\)一定比\(f[1]\)优，接的话也不会影响复杂度）；如果\(a_i=2\)，那么它可以作为\(2\)接在\(f[1],f[2]\)，或者作为\(4\)接在\(f[3],f[4]\)后面。这样做\(\text{LIS}\)，时间复杂度是\(O(n)\)的。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;

int f[5];
int a[100100];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        if(a[i]==1)
        {
            ++f[1];
            f[3]=max(f[2],f[3])+1;
        }
        else
        {
            f[4]=max(f[3],f[4])+1;
            f[2]=max(f[1],f[2])+1;
        }
            
    }
    printf("%d\n",max(max(max(f[1],f[2]),f[3]),f[4]));
    return 0;
}