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

作者: wjyyy 分类: DP,打表/找规律,构造,解题报告 发布时间: 2018-11-03 09:32

点击量:13

 

    考试读错题了导致没有\(\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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */