题面

给出$n*m$个矩阵，从第一列开始，一列一列访问元素，依次记元素为$S1,S_2,…S{nm}$，则$k$的价值为相邻两个元素差的绝对值的最小值，即$k=min{|S1 - S_2|,|S_2 - S_3|,…,|S{nm-1} - S_{nm}|}$

现在可以改变任意行的顺序，求$k$的最大值

解题思路

正解应该是状压DP

但是以下讲的是另一种玄学做法——搜索

当然啦~，直接爆搜是不行的，在一切之前，我们先研究一下题目

然后做一些预处理

比如：

1、改变的是行的顺序，因此任意两行之间的最小差值可以预先求出来

9 9
10 8
$\large \color{red}5$ $\large \color{red}3$
$\large \color{red}4$ $\large \color{red}3$

图中两行的差值就是 $0$ 吧，然后类似处理其他行

就是先把一些固定的值处理出来

2、可以把两行分别在头尾的代价处理出来

5 $\large \color{red}3$
9 9
10 8
$\large \color{red}4$ 3

这里的顺序和先前不一样是想说明行的顺序是可以改变的！这时要处理的比较特殊，想象一下转换成一条链后，标红的是相邻的，我们也依次把这样的差值处理出来

预处理完后

原本和 $m$ 有关的数据就只和 $n$ 有关了，而 $n$ 的范围有那么小，于是开始乱搞

然后我们就搜索，枚举 $n$ 的全排列

当然这是不可能的，不炸就怪，肯定要加剪枝

然后就加——最优性剪枝 其实我没学过深搜的优化技巧

并且加入一个线段树的 $lowbit$ 操作，差不多就挺快的了

其实大致算一下：

也不多啦~

加了优化之后，有很大的减少的

先上代码，注释掉的读优不用管

Code：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
//#define getchar() *(pos++)
#define N 20
#define M 10010
using namespace std;
struct node{
    int to,nxt,cost;
    node(int a,int b):to(a),cost(b){    }
    node(){    }
}b[M<<1];
int head[N],n,m,a[N][M],s[N][N],p[N][N],res,ans,bef,Total;
int f[1<<20][20],C[100010];
//char bf[1<<25],*pos;
//int read(){int s=0;char c=getchar();
//    while(!isdigit(c))c=getchar();
//    while(isdigit(c)){s=(s<<1)+(s<<3)+c-'0';c=getchar();}
//    return s;
//}
void DFS(int k,int res,int t,int last)
{//k表示做
    if(res<=ans) return;//ans表示目前的最大值
    if(k==n){
        ans=max(ans,min(res,p[bef][last]));
        return;
    }
    int cur=Total-t,j;
    while(cur){//树状数组的lowbit
        j=C[cur&(-cur)];//对应到回原来的编号-1，因为第一位 1=2^0
        if(s[last][j+1]>ans) 
            DFS(k+1,min(res,s[last][j+1]),t|(1<<j),j+1);
        cur-=cur&(-cur);
    }
}
int main()
{
    int i,j,k;
//    bf[fread(bf,1,1<<25,stdin)]='\0',pos=bf;
    n=read();m=read();k=1;
    for(i=0;i<=16;i++)//2^k对应到k，方便后面知道是哪一位
        C[k]=i,k<<=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a[i][j]=read();
    for(i=1;i<=n;i++)//预处理 第1条
        for(j=1;j<i;j++)
        {
            res=INF;
            for(k=1;k<=m;k++)
                res=min(res,abs(a[i][k]-a[j][k]));
            s[i][j]=s[j][i]=res;
        }
    for(i=1;i<=n;i++)//预处理 第二条
        for(j=1;j<=n;j++)
        {
            res=INF;
            for(k=1;k<m;k++)
                res=min(res,abs(a[i][k+1]-a[j][k]));
            p[i][j]=res;
        }
    if(n==1){printf("%d",p[1][1]);return 0;}//这种情况不特判也没关系
    Total=(1<<n)-1;//用于DFS中取反操作，是我太菜了，只会这种方法
    for(i=1;i<=n;i++)//bef表示记录首行，方便最后判断
        bef=i,DFS(1,INF,1<<(i-1),i);
    printf("%d",ans);
    return 0;
}

关于时间复杂度

->Sinner 这位大佬说：时间复杂度是不正确的！ 我（瑟瑟发抖）：根据玄学，跑得超快的，因为两行之间的最小值比较难卡，所以时间还是比较稳定的我们不是理论派

好吧，此份题解仅供参考

devil.