P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

Bulyly · 2022-11-13 13:12:27 · 题解

前言

正愁着找不到题练树状数组这不就来了吗？

解析

• 这是一道好写且好想的题，核心是用 O(n\log n) 的算法来求最长不下降子序列，所以二分或者树状数组等都是可以的，这里我写的是树状数组。这样就不涉及区间 LIS 等其他东西就没必要用线段树了

• 首先正着做一遍朴素的最长不下降子序列得到 f[i] 表示以 i 为结尾的最长不下降子序列，同理，再反着求一遍最长不上升子序列得到 g[i] 表示以 i 为开始的最长不上升子序列。

• 接着就是思考如何合并，首先我们很容易发现改变的数越多解一定是更优的，假如你将前 i 个数修改，得到的答案一定不会少于修改前 i - 1 数。

• 这样的话就可以采取贪心策略，将位置 i 的前 k 个数都改成与其相同的值然后再去找一个位置 i - k - 1 之前的位置 j 能与其拼接且 f[j] 最大，再加上 g[i]，最后打擂取一个 \max。

update on 11.24：感谢 Halcyflict 提供的 hack 数据。之前的考虑存在一种漏洞，那就是无论如何都无法修改到最后一个点，那需要怎么做呢，在数组末尾在加上一个最大值即可，这样既不会影响答案，也能保证修改到原来最后一个数。注意，数组已经被离散化过所以添加的数应为不同数个数 +1。

• code：

  #include <cstdio>
  #include <cstring>
  #include <iostream>
  #include <algorithm>
  #define RT register
  #define N 100010
  using namespace std;
  int n,k,m,ans;
  int a[N],s[N],f[N],tr[N],g[N];
  inline int qmax(int x)
  {
  int ans(0);
  for(;x;x-=x&-x)  ans=max(ans,tr[x]);
  return ans;
  }
  inline void add(int x,int y){for(;x<=n;x+=x&-x)  tr[x]=max(tr[x],y);}
  int main()
  {
  memset(tr,0,sizeof(tr));
  scanf("%d%d",&n,&k);
  for(RT int i=1;i<=n;i++)  scanf("%d",&a[i]),s[i]=a[i];
  sort(s+1,s+n+1);
  m=unique(s+1,s+n+1)-s-1;
  for(RT int i=1;i<=n;i++)  a[i]=lower_bound(s+1,s+m+1,a[i])-s;//离散化
  for(RT int i=1;i<=n;i++)    f[i]=qmax(a[i])+1,add(a[i],f[i]);
  memset(tr,0,sizeof(tr));
  for(RT int i=n;i>=1;i--)    g[i]=qmax(n-a[i]+1)+1,add(n-a[i]+1,g[i]);
  memset(tr,0,sizeof(tr));
  a[n+1]=m+1;
  for(RT int i=k+2;i<=n+1;i++)
  {
      add(a[i-k-1],f[i-k-1]),ans=max(ans,k+g[i]+qmax(a[i]));
  }
  if(k>=n-1)  ans=max(ans,n);//很重要
  printf("%d\n",ans);
  return 0;//perfect ending !
  }

完结撒花~