思路

写个不太一样的，二分答案的题解。 考虑二分 k 。为了验证当前答案的可行性，先预处理出矩阵 c[i][j] 表示第 i 行与第 j 行间差的绝对值的最大值是否大于等于 k 。这个可以 O(n^2m) 做到。然后考虑状压 DP 。f[S][i][j] 表示当前处理过的行的状态为 S ，首行是 i ，末行是 j 时答案是否可行。容易推出 DP 方程 f[S][i][j]=\bigoplus_{k\in S\wedge c[j][k]} f[S\setminus j][i][k] ，其中 \bigoplus 表示或，S\setminus j 表示 S 除去 j 的元素。这样就可以 O(n) 转移得到每个状态，最后再暴力枚举首行和末行，总时间复杂度 O(2^nn^3log10^9) ，并不能过。 观察到 f 其实是一个只有 0 和 1 的 bool 数组，而最后一维 j 也是 O(n) 级别的，我们可以考虑把最后一维压掉。f[S][i] 表示当前处理过的行的状态为 S ，首行是 i，末行使答案可行的状态。同时我们把最开始预处理的矩阵 c 的每行也压成一个 int 。这样做就可以使状态数少一个 n ，转移仍是 O(n) 的，因此时间复杂度为 O(2^nn^2log10^9) ，能过。 代码中为了优化速度，把 f 数组小的一维放在了前面。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=20;
const int MAXM=11000;
const int MAXS=70000;
int n, m;
int a[MAXN][MAXM];
int c[MAXN], f[MAXN][MAXS];
bool chk1(int x, int y, int k)
{
    for (int i=1; i<=m; i++)
        if (abs(a[x][i]-a[y][i])<k) return 0;
    return 1;
}
bool chk2(int x, int y, int k)
{
    for (int i=1; i<m; i++)
        if (abs(a[x][i+1]-a[y][i])<k) return 0;
    return 1;
}
bool check(int k)
{
    memset(c, 0, sizeof c);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (chk1(i, j, k)) c[i]|=1<<j-1;
    memset(f, 0, sizeof f);
    for (int i=1; i<=n; i++)
        for (int s=1; s<1<<n; s++)
        {
            if (!(s&1<<i-1)) continue;
            if (s==1<<i-1) f[i][s]=1<<i-1;
            else
            {
                for (int j=1; j<=n; j++)
                    if (s&1<<j-1&&f[i][s^1<<j-1]&c[j])
                        f[i][s]|=1<<j-1;
            }
        }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (chk2(i, j, k)&&f[i][(1<<n)-1]&1<<j-1) return 1;
    return 0;
}
int main()
{
//  freopen("CF1102F.in", "r", stdin);
//  freopen("CF1102F.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            scanf("%d", &a[i][j]);
    int l=0, r=1E9;
    while (l<r)
    {
        int mid=l+r+1>>1;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n", l);
    return 0;
}