Good Grid

题目描述

有一个由 $N$ 行 $N$ 列方格组成的网格。令 $(i,j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的方格。 这些方格必须被涂成 $C$ 种颜色之一，从 颜色 $1$ 到 颜色 $C$。初始时，$(i,j)$ 被涂成颜色 $c_{i,j}$。 当对于满足 $1 \leq i,j,x,y \leq N$ 的所有 $i,j,x,y$，下述条件成立时，我们称该网格为一个 良好 网格：

如果 $(i+j) \% 3=(x+y) \% 3$，则 $(i,j)$ 的颜色与 $(x,y)$ 的颜色相同。 如果 $(i+j) \% 3 \neq (x+y) \% 3$，则 $(i,j)$ 的颜色与 $(x,y)$ 的颜色不同。

这里，$X \% Y$ 表示 $X$ 模 $Y$。 我们将重涂零个或多个方格，使得网格成为一个良好网格。 对于一个方格，当该方格在重涂前的颜色为 $X$、重涂后的颜色为 $Y$ 时，其错误代价为 $D_{X,Y}$。 求所有方格的错误代价总和的最小可能值。

输入格式

输入从标准输入按照以下格式给出： $N$ $C$ $D_{1,1}$ $...$ $D_{1,C}$ : $D_{C,1}$ $...$ $D_{C,C}$ $c_{1,1}$ $...$ $c_{1,N}$ : $c_{N,1}$ $...$ $c_{N,N}$

输出格式

如果所有方格的错误代价的最小可能和为 $x$，则输出 $x$。

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

3

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

428

提示

$1 \leq N \leq 500$ $3 \leq C \leq 30$ $1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)$ $1 \leq c_{i,j} \leq C$ 输入中的所有值均为整数。将 $(1,1)$ 重涂为颜色 $2$。$(1,1)$ 的错误代价变为 $D_{1,2}=1$。 将 $(1,2)$ 重涂为颜色 $3$。$(1,2)$ 的错误代价变为 $D_{2,3}=1$。 将 $(2,2)$ 重涂为颜色 $1$。$(2,2)$ 的错误代价变为 $D_{3,1}=1$。

在此情况下，所有方格的错误代价之和为 $3$。 注意 $D_{i,j} \neq D_{j,i}$ 是可能的。

标签: AtCoder|abc099D

来源

AtCoder|abc099D