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

_wzb_ · 2025-04-01 14:06:10 · 题解

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

前置芝士：树状数组（不清楚的去问问度娘）。

题目大意：求修改 k 个数之后的最长不下降子序列。

思路：用 dp_i 表示从第 1 个到第 i 个数的最长不下降子序列，用 pd_i 表示从第 1 个数到第 n 个数的最长不下降子序列，要维护一个区间的最大值可以用什么？没错就是树状数组，用树状数组维护当前区间的最长不下降子序列，因为可以修改连续的 k 个数。所以我们可以利用这 k 个数让 dp_i 和 pd_i 连接起来。不清楚的可以看看图片，我们可以得出结果是 \max(dp_i+k+pd_i-1,ans)。

如图：

（有点抽象但是已经认真画了）

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a[N],k,dp[N],pd[N],t[N],ans=0;
int lowbit(int x)//树状数组 
{
    return x&(-x);//lowbit不过多解释不知道的可以去度娘看看 
}
void up(int x,int v);//维护x节点的最大值 修改x的值 
int q(int x);//维护最长不下降子序列 
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=1;
        pd[i]=1;//初始化 
    }
    for(int i=0;i<N;i++)t[i]=1;
    dp[1]=1;
    pd[n]=1;
    for(int i=2;i<=n;i++)//求从1到i的最长不下降子序列 
    {
        dp[i]=q(a[i]);//找前缀最大值 
        up(a[i],dp[i]+1);//更新树状数组 
    } 

    for(int i=0;i<N;i++)t[i]=1;//初始化 
    for(int i=n-1;i>=1;i--)//求从i到n的最长不下降子序列 
    {
        pd[i]=q(N-a[i]);//因为要从右向左找 但是树状数组的逻辑默认是从小到大维护值的所以要取反 
        up(N-a[i],pd[i]+1);//更新树状数组 
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp[i]+k+pd[i]-1);//枚举节点找最优 
    }
    cout<<min(ans,n)<<"\n";
    return 0;
}
int q(int x)//
{
    int ans=0;//初始化最大值为0 
    while(x>0)//从x开始向下遍历 
    {
        ans=max(ans,t[x]);//更新当前区间的最大值 
        x-=lowbit(x);//移动到左边的节点 
    }
    return ans;
}
void up(int x,int v)//维护x节点的最大值 
{
    while(x<=N)//从位置x开始，向上更新树状数组
    {
        t[x]=max(t[x],v);// 更新当前节点为最大值
        x+=lowbit(x);// 移动到父节点 
    }
    return ;
}