U330741 RGB

逛 B 栈的时候无意中见到的。给出个多项式算法或者证明是 NPC 都行。

给定 $n \times m$ 个三元组。要求将这些这些三元组不重复地放置到一个 $n \times m$ 的平面上。 两个三元组 $(a , b , c)$ 和 $(x , y , z)$ 的差定义为 $|a - x| + |b - y| + |c - z|$。一个位置的贡献定义为它和周围四个三元组的差之和。 求所有位置的贡献之和最小是多少。如果可以的话请构造一组贡献最小的方案。

无

无