cf 1102F Elongated Matrix

전송문:https://codeforces.com/contest/1102/problem/F You are given a matrix a, consisting of n rows and m columns. Each cell contains an integer in it.
You can change the order of rows arbitrarily (including leaving the initial order), but you can’t change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be s1,s2,…,snm.
The traversal is k-acceptable if for all i (1≤i≤nm−1) |si−si+1|≥k.
Find the maximum integer k such that there exists some order of rows of matrix a that it produces a k-acceptable traversal.
Input
The first line contains two integers n and m (1≤n≤16, 1≤m≤104, 2≤nm) — the number of rows and the number of columns, respectively.
Each of the next n lines contains m integers (1≤ai,j≤109) — the description of the matrix.
Output
Print a single integer k — the maximum number such that there exists some order of rows of matrix a that it produces an k-acceptable traversal.
Examples
input

4 2
9 9
10 8
5 3
4 3

output

5

제목: n*m의 숫자 행렬을 주면 임의의 두 줄의 순서를 교환한 다음에 열 순서에 따라 전체 행렬을 훑어보고 길이가 nm인 서열을 얻을 수 있다.임의로 줄을 바꾼 다음 행렬에서 얻을 수 있는 시퀀스에서 두 개의 수차값과 인접한 최소값을 최대로 해야 합니다.해법: 줄을 무시하고 각 줄을 하나의 단독 노드로 간주한다. 만약에 i줄이 j줄과 인접하면 그들 사이에는 권한이 하나 있는데 크기는min(abs(a[i][k]-a[j][k])이고 k는 열을 나타내며 값은 1~m이다.1행과 n행에 대해서도 그들 사이에는 권한이 있다. 만약에 i행을 1행으로 하고 j행을 n행으로 한다면 그들 사이의 권한은min(abs(a[i][k], a[j][k+1])이고 k의 가치는 1~m-1이다.만약 우리가 1행과 n행 사이의 값을 소홀히 한다면 이 문제는 최소 하미턴 거리를 구하고 직접 dp를 구하면 된다.1행과 n행 사이의 값을 고려하려면 1행과 n행을 매거해야 한다.

/*
c1[i][j]   i，j       
c2[i][j]     i       ，j          
*/
#include

using namespace std;
const int maxn = 1e4 + 5;
const int inf = 0x3f3f3f3f;
int a[17][maxn], c1[17][17], c2[17][17], dp[1 << 17][17];
int n, m;
int cal(int mask, int u)
{
    if(dp[mask][u] != -1) return dp[mask][u];
    dp[mask][u] = 0;
    for(int v = 0; v < n; v++){
        if(v == u) continue;
        if((mask >> v) & 1)
            dp[mask][u] = max(dp[mask][u], min(c1[v][u], cal(mask ^ (1 << u), v)));
    }
    return dp[mask][u];
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            c1[i][j] = c2[i][j] = inf;
            for(int k = 0; k < m; k++) c1[i][j] = min(c1[i][j], abs(a[i][k] - a[j][k]));
            for(int k = 0; k < m - 1; k++) c2[i][j] = min(c2[i][j], abs(a[i][k] - a[j][k + 1]));
        }
    }
    int ans = 0;
    //         1   n 
    for(int i=0;i<n;i++){
        memset(dp,-1,sizeof dp);
        for(int j=0;j<n;j++)
            dp[1<<j][j]=i==j?inf:0;  //    inf    i    1 
        for(int j=0;j<n;j++)
            ans=max(ans,min(c2[j][i],cal((1<<n)-1,j)));
    }
    cout << ans << '
';
    return 0;
}