F. Elongated Matrix

F. Elongated Matrix
把n个行当成一个个点，点之间的距离就是相同位置差值的最大值

1. 枚举起点
2. 以这个起点出发求状压dp，dp[S][i] 代表最后到达的点是i，状态是S
3. 枚举终点

#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int N = 16;
const int M = 10000;
const int INF = 1000000000;

int aa[N][M], kk[N][N], dp[1 << N][N];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &aa[i][j]);
	for (int i1 = 0; i1 < n; i1++)
		for (int i2 = i1 + 1; i2 < n; i2++) {
			int k = INF;
			for (int j = 0; j < m; j++)
				k = min(k, abs(aa[i1][j] - aa[i2][j]));
			kk[i1][i2] = kk[i2][i1] = k;
		}
	int ans = 0;
	for (int s = 0; s < n; s++) {
		for (int b = 0; b < 1 << n; b++)
			fill_n(dp[b], n, 0);
		dp[1 << s][s] = INF;
		for (int b = 0; b < 1 << n; b++)
			for (int i_ = 0; i_ < n; i_++)
				if (dp[b][i_])
					for (int i = 0; i < n; i++)
						if (!(b & 1 << i))
							dp[b | 1 << i][i] = max(dp[b | 1 << i][i], min(dp[b][i_], kk[i_][i]));
		for (int i = 0; i < n; i++) {
			int k = dp[(1 << n) - 1][i];
			for (int j = 0; j + 1 < m; j++)
				k = min(k, abs(aa[i][j] - aa[s][j + 1]));
			ans = max(ans, k);
		}
	}
	printf("%d\n", ans);
	return 0;
}