• 【学习笔记】「JOI Open 2022」长颈鹿


    有点难😅

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

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

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

    看起来状态数还是很大😅

    使用扫描线+树状数组优化转移,可以做到 O ( n n log ⁡ n ) O(n\sqrt{n}\log n) O(nn logn)

    发现我们实际上不用把 8 8 8种情况都讨论完,上下左右四种情况都是对称的,因此将坐标翻转一下就好了。

    #include
    #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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
  • 相关阅读:
    面试必备:Thread、Runnable、Callable、Future、FutureTask,谈谈他们的关系?(荣耀典藏版)
    [ C++ ] STL_stack(栈)queue(队列)使用及其重要接口模拟实现
    R 语言画图中英文字体解决方案
    【AIGC核心技术剖析】Hotshot-XL 一种 AI 文本转 GIF 模型(论文 + 代码:经过训练可与Stable Diffusion XL一起使用)
    SSM二手交易网站
    产品经理和项目经理谁才是项目管理界的NO.1?
    【DevOps】路由与路由器详细介绍:原理、功能、类型及应用场景
    算法面试题:Two Sum问题
    23-356、基于51单片机智能药盒报警时钟存储语音播报设计-CSDN
    Kafka偏移量自动提交设置
  • 原文地址:https://blog.csdn.net/cqbzlydd/article/details/132816696