cf531F

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

cf531F

链接

题意

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

题解

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