洛谷-P9147 题解

正文

最坏时间复杂度：\(\mathcal{O}(n)\)

真不愧是签到题，差点没签上。。。

我相信题意各位肯定很理解了，非常简单，但如何解决就是个问题。

首先考虑朴素解法，建立一个求最长连续子序列的函数 \(F\)，如果用双指针的话，可以优化到 \(\mathcal{O}(n)\)；然后是枚举每个 \(a_i\)，又是一个 \(\mathcal{O}(n)\)；易发现，每次枚举 \(a_i\) 更改，我们不需要一个一个数字枚举，只需要枚举三次就行，\(a_i\) 前后的两个数字会构成三个范围，只要分别考虑将 \(a_i\) 修改成这三个范围之内的数即可。

总计 \(\mathcal{O}(n^2)\)。

如何优化呢？

注：以后所提及的单调上升子序列皆为最优。

可以发现，我们并不需要每个枚举。假设一个数处于一个单调上升序列中，把它修改了反而会破坏序列的单调性。因此我们只需枚举每个单调上升子序列首末端，来判断它是否可以和在它前面或后面的单调上升子序列合并组成一个更长的单调上升子序列。

我们预处理 \(l_i\)，\(st_i\)，\(en_i\)，分别代表第 \(i\) 个单调上升子序列的长度、开端位置、末端位置。

假设每个单调上升子序列无法相互合并，那最好的方法就是把最长的单调上升子序列首端或末端更改，让这个最长的单调上升子序列的长度再加一。

即把答案设为 \(\max l_i+1\).

考虑合并，见下，以后设 \(S_i\) 表示原序列第 \(i\) 个数。

1 3 2 6 7。本例中有 2 个单调上升子序列，我们把第 2 个单调上升子序列的开头修改成 4（或者其它）即可。我们可得知：若 \(S_{st_i+1}-S_{en_{(i-1)}}>1\)，考虑合并。

当然，不要忘考虑这样的情况：1 4 3 5 7，把第 1 个单调上升子序列的末尾修改成 2 即可，即：若 \(S_{st_i}-S_{en_{(i-1)}-1}>1\)，考虑合并。

大体完毕，但，还有特判！！！若 \(S\) 只有一个单调上升子序列，那就输出它的长度，因为它已经是最长了。

总计 \(\mathcal{O}(n)\)。

#include<iostream>
using namespace std;
const int N=1e6+15;
struct P{int l,st,en;}s[N];
int a[N],n,ln,t,mx,cnt,ans;
int main(){
  ios::sync_with_stdio(0),cin.tie(0);
  cin>>n,t=1;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    if(mx<a[i]) ln++,mx=a[i];
    else s[++cnt].st=t,s[cnt].en=i-1,s[cnt].l=ln,
        ln=1,mx=a[i],t=i;
  }
  if(s[cnt].en!=n) s[++cnt].st=t,s[cnt].en=n,s[cnt].l=ln;
  if(cnt==1) cout<<n,exit(0);
  for(int i=1;i<=cnt;i++) ans=max(ans,s[i].l+1);
  for(int i=2;i<=cnt;i++)
    if(a[s[i].st+1]-a[s[i-1].en]>1||a[s[i].st]-a[s[i-1].en-1]>1)
      ans=max(ans,s[i].l+s[i-1].l);
  cout<<ans;
}

完结！！

后附

日志

v1.0 on 2023.03.15: 发布