#include<bits/stdc++.h>
using namespace std;
int n,f[109][109],g[109][109],m[109][109],q[109][109],a[109],r,w,o,z;//f[r][d]:[k,k+r-1]在[d,d+r]时最大的b,g[r][d]:最大值位置,m[r][d]:消除最大值后左端点的位置,q[r][d]:消除最大值后的区间长度
bool h[109][109];//h[r][d]:[次大值在最大值右边]
int main(){
    cin>>n;
    if(n==1) return cout<<"1",0;
    for(int i=1;i<=n;++i) f[1][i]=0,g[1][i]=i,h[1][i]=0,m[1][i]=0,q[1][i]=0;
    for(int i=2;i<=n;++i){
        for(int u=1,v=i;v<=n;++u,++v) for(int s=u;s<v;++s){r=s-1,w=0;if(s+1+r-1<n) s+1+r>=n?(w=r-2+(s+1+r-1<n),o=z=0):(w=f[z=min(v+r,n-1)-(s+1+r)+1][o=s+1+r]+r);if(w>f[i][u]) f[i][u]=w,g[i][u]=s,m[i][u]=o,q[i][u]=z,h[i][u]=1;}//次大值在s右边
        for(int u=1,v=i;v<=n;++u,++v) if(n+1!=u+v&&h[i][n+1-v]){w=f[i][n+1-v];if(f[i][u]<w) f[i][u]=w,h[i][u]=0,g[i][u]=n+1-g[i][n+1-v],m[i][u]=n+1-(m[i][n+1-v]+q[i][n+1-v]-1),q[i][u]=q[i][n+1-v];}//次大值在s左边
    }
    a[1]=1,a[n]=2;
    int u=2,v=n-1,d=2,l=3,r=n;
    while(1){
        if(u>v) break;
        if(u==v){a[d]=l;break;}
        if(!f[v-u+1][u]){iota(a+d,a+d+v-u+1,l);break;}
        int t=g[v-u+1][u];
        bool s=h[v-u+1][u];
        o=m[v-u+1][u],z=q[v-u+1][u];
        if(s){
            for(int i=u;i<t;++i) a[i+d-u]=l++;
            for(int i=t+1+z;i<=v;++i) a[i+d-u]=l++;
            a[t+d-u]=r--;
            d=t+d-u+1,u=o,v=u+z-1;
        }
        else{
            for(int i=t+1;i<=v;++i) a[i+d-u]=l++;
            for(int i=u;i<=t-1-z;++i) a[i+d-u]=l++;
            a[t+d-u]=r--;
            u=o,v=u+z-1;
        }
    }
    for(int i=1;i<=n;++i) cout<<a[i]<<" ";
}

该代码在 $n \in [1,100] ∩ \mathbb{Z^+}$ 时，仅会在 $n=12$ 时比标准答案的计时器少 $1$

萌新求助！