nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf531F

链接

https://codeforces.com/contest/1102/problem/F

题意

        给你一个最多16行1e4列的矩阵A，对矩阵按列优先遍历，得到一维数组B，当然，此时也可以输A是B按列优先访问得到的二维数组，定义一维数组的权为任意相邻两个数的差的绝对值的值小值，你可以对A进行行互换，但不可列互换，问换完之后，对矩阵按列优先遍历之后的B的权的最大值是多少。

题解

        分析发现与列数量无关，再分析，发现行互换，相当于在对行重排列，再分析发现这其实是一个Hamiltonpath。枚举起点和终点即可。