【学习笔记】「JOI Open 2022」长颈鹿-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学习笔记】「JOI Open 2022」长颈鹿。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有点难😅

不难写出 $O(n^3)$ 的 $D P$ ，考虑不一样的做法🤔

发现答案和 $L I S / L D S$ 有关系。如果是左上角/右上角那么加入 $L D S$ ，否则加入 $L I S$ ，容易发现原序列被拆分成了一个 $L I S$ 和 $L D S$ ，因此答案期望不会超过 $\sqrt{n}$ 。

发现可以设 $f_{i,j,k}$ 表示以 $i,p_i)$ 为矩阵的一角，向 $4$ 个方向，包含 $k$ 个关键点时正方形边长的最小值。枚举 $k - 1$ 情况下的所有正方形然后转移即可，转移的条件是 $k - 1$ 情况下的矩阵能够被完全包含。~~有点抽象~~ 这样复杂度 $O(n^2\sqrt{n})$ 。

看起来状态数还是很大😅

使用扫描线+树状数组优化转移，可以做到 $O(n\sqrt{n}\log n)$ 。

发现我们实际上不用把 $8$ 种情况都讨论完，上下左右四种情况都是对称的，因此将坐标翻转一下就好了。文章来源地址https://www.toymoban.com/news/detail-709059.html

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
int n,p[8005],res,f[8005][4],bit[8005];
vector<pair<int,pair<int,int>>>now,nxt;
void add(int &x,int y){
    x=max(x,y);
}
vector<pair<int,pair<int,int>>>v,v2;
bool cmp(pair<int,pair<int,int>>x,pair<int,pair<int,int>>y){
    return x.se.se-x.se.fi<y.se.se-y.se.fi;
}
void add(int x,int y){
    for(;x<=n;x+=x&-x)bit[x]=min(bit[x],y);
}
int query(int x){
    int tot(inf);
    for(;x;x-=x&-x)tot=min(tot,bit[x]);
    return tot;
}
int rev(int x){
    return n-x+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++){
        now.pb({0,{i,p[i]}});
    }res=n-1;
    for(int i=2;;i++){
        nxt.clear();memset(f,0x3f,sizeof f);
        for(int k=0;k<4;k++){
            v.clear(),v2.clear();
            for(int j=1;j<=n;j++){
                int x=(k&1)?j:(n-j+1),y=(k&2)?p[j]:(n-p[j]+1);
                v.pb({j,{x,y}});
            }sort(v.begin(),v.end(),cmp);
            for(auto e:now){
                int l1=e.se.fi,r1=e.se.se,l2=l1+e.fi,r2=r1+e.fi;
                if(!(k&1))l1=rev(l1),l2=rev(l2);if(!(k&2))r1=rev(r1),r2=rev(r2);
                if(l1>l2)swap(l1,l2);if(r1>r2)swap(r1,r2);
                v2.pb({e.fi,{l1,r1}});
            }sort(v2.begin(),v2.end(),cmp);
            memset(bit,0x3f,sizeof bit);
            int it=0;
            for(auto e:v){
                int p=e.fi,x=e.se.fi,y=e.se.se;
                while(it<v2.size()&&v2[it].se.se-v2[it].se.fi<=y-x){
                    add(rev(v2[it].se.se),v2[it].se.fi+v2[it].fi);
                    it++;
                }f[p][k]=min(f[p][k],query(rev(y)-1)-x);
            }
            reverse(v.begin(),v.end()),reverse(v2.begin(),v2.end());
            it=0;memset(bit,0x3f,sizeof bit);
            for(auto e:v){
                int p=e.fi,x=e.se.fi,y=e.se.se;
                while(it<v2.size()&&v2[it].se.se-v2[it].se.fi>=y-x){
                    add(rev(v2[it].se.fi),v2[it].se.se+v2[it].fi);
                    it++;
                }
                f[p][k]=min(f[p][k],query(rev(x)-1)-y);
            }
            for(int j=1;j<=n;j++){
                int l1=j,r1=p[j],l2=((k&1)?f[j][k]:-f[j][k])+l1,r2=((k&2)?f[j][k]:-f[j][k])+r1;
                if(l1>l2)swap(l1,l2);if(r1>r2)swap(r1,r2);
                if(l1>=1&&l2<=n&&r1>=1&&r2<=n){
                    nxt.pb({f[j][k],{l1,r1}});
                }
            }
        }
        if(nxt.size()==0){
            break;
        }
        now=nxt,res=n-i;
    }cout<<res;
}