没想到Div.3里还有这么好的题
其实就是求Hamilton路径
预处理 \(d\) 数组:
\(d1_{i,j}\) 表示第 \(i,j\) 行相邻产生的最小值
\(d2_{i,j}\) 表示第 \(i,j\) 行分别为最后一行和第一行时产生的最小值
将每一行当成一个点,任意两点 \(i,j\) 间连一条边权为 \(d1_{i,j}\) 的边
在图中求一条经过边权中最小值最小的Hamilton路径
设 \(f_{i,j}=min(s_{i,j},d2_{j,i})\)
所有 \(f\) 的最小值即为 \(ans\)
求Hamilton路径用状压dp
总时间复杂度为 \(O(n^2m+2^nn^3)\)
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 16, M = 10000, INF = 0x3f3f3f3f;
int n, m, a[N][M], d1[N][N], d2[N][N], f[N][N];
int s[1<<N][N], ans;
void Hamilton(int x) {
memset(s, 0, sizeof(s));
s[1<<x][x] = INF;
for (int i = 1; i < (1 << n); i++)
for (int j = 0; j < n; j++)
if ((i >> j) & 1)
for (int k = 0; k < n; k++)
if (((i ^ (1 << j)) >> k) & 1)
s[i][j] = max(s[i][j], min(s[i^(1<<j)][k], d1[k][j]));
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
memset(d1, 0x3f, sizeof(d1));
memset(d2, 0x3f, sizeof(d2));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++)
d1[i][j] = min(d1[i][j], abs(a[i][k] - a[j][k]));
for (int k = 1; k < m; k++)
d2[i][j] = min(d2[i][j], abs(a[i][k-1] - a[j][k]));
}
for (int i = 0; i < n; i++) {
Hamilton(i);
for (int j = 0; j < n; j++)
ans = max(ans, min(s[(1<<n)-1][j], d2[j][i]));
}
cout << ans << endl;
return 0;
}