UVA1471 防线 Defense Lines

· · 题解

一、前言

这是一道非常好的运用数据结构优化的题目，本篇题解将详细讲解解题思路，一是给做这题的人提供想法，二是让自己更好地掌握这种方法。

二、题意

在一个长度为 n 的序列之中，你需要删去一个连续子序列，使得剩下的序列中连续递增子序列长度最长。

三、思路

显然，在删去中间的连续子序列之后，得到的最长连续递增子序列是由两个序列合并在一起的得到的，因此我们需要两个数组：一个 st[i]，用来存储以 i 开始的最长连续递增子序列的长度，另一个 ed[i]，用来存储以 i 结尾的最长连续递增子序列的长度，到时候以 ed[i]+st[j] 来更新答案。

a[i] 5 3 4 9 2 8 6 7 1
ed[i] 1 1 2 3 1 2 1 2 1

我们可以发现，对于数值 6，数值 4 比它小，同时它的 ed 值（1）还比 4 的（2）要小，那它就没有保留意义。（数值比它小说明比它更容易拼成一个递增区间，ed 值比它大说明对答案贡献更大），因此得出结论：对于一个区间的左端点 j,若有 j' 满足 a[j']<=a[j] 且 ed[j']>ed[j]，那么 j 肯定不满足条件。

四、知识点

set 的一些操作

set<node>::iterator it;
node last=*it;
it++;

set<node>::iterator it =s.lower_bound(now);

五、代码

#include<cstdio>
#include<set>
using  namespace std;

const int N=2e5+7;
int t,n,a[N],ed[N],st[N],ans; 
bool flag;

struct node//定义结构体存储a和ed 
{
    int a,ed;

    node(int a,int ed)://构造函数，为结构体赋值 
        a(a),ed(ed){} 

    bool operator < (const node &x) const//重载运算符 
    {
        return a<x.a;
    }
};

set<node>s;//set维护序列 

void pre()//预处理出st和ed数组 
{
    //ed[i]是以i结束的最长连续递增子序列长度
    ed[1]=1;
    for(int i=2;i<=n;i++)
        if(a[i]>a[i-1])
            ed[i]=ed[i-1]+1; 
        else
            ed[i]=1; 

    //st[i]是以i开始的最长连续递增子序列长度 
    st[n]=1;
    for(int i=n-1;i>=1;i--)
        if(a[i]<a[i+1])
            st[i]=st[i+1]+1;
        else
            st[i]=1;    
} 

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        pre();

        s.clear();
        s.insert(node(a[1],ed[1]));
        ans=1;
        for(int i=2;i<=n;i++)
        {
            node now(a[i],ed[i]);//由于结构体里定义了构造函数，这里可以直接赋值 
            set<node>::iterator it =s.lower_bound(now);//二分查找第一个>=now的值

            flag=true;//flag为true表示新加入的元素可以保留，反之要删去

            if(it!=s.begin())
            {
                node last=*(--it);//last为满足a[j]<a[i]最大的a[j]
                ans=max(ans,st[i]+last.ed);//更新答案
                if(now.ed<=last.ed)//如果last排在now前面，且now的ed比last小，那now就没有保留价值了 
                    flag=false; 
            }

            if(flag)
            {
                    s.erase(now);//如果说新插入的元素可以保留，说明它 ed 一定比老的要大，重新更新位置
                        s.insert(now);
                    it=s.find(now);
                    it++;
                        while(it != s.end() && (*it).a > now.a && (*it).ed <= now.ed)//删去后面没有保留意义的元素 
                        s.erase(it++);
            }
        }   

        printf("%d\n",ans);

    }

    return 0;
}

六、后记