考虑搜索，发现复杂度爆炸
贪心，正确性过低(~~实测爆炸~~)
于是，~~发现~~这题是模拟退火
这里不讲解退火的定义了，初学退火可以去平衡点
退火本身维护一个答案图像，答案的q，当前图像，当前的q
暴力根据计算图像计算q即可
关于这题我们发现如果任由其随机，可能会导致偏差太大
但如果过多修正偏差，可能导致其跃出局部最优解的能力降低
于是我加了这么一句话
if (curq - ansq >= (temp * 90)){
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j)
cur_map[i][j] = ans_map[i][j];
curq = ansq;
}
即根据当前温度及时修正偏差，温度越高，偏差容忍度越高
最后放个代码(不保证一直AC)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ll long long
#define ri register int const double DEL = 0.00001;
const double DELTA = 0.99999; inline ll read(){
ll x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} int n, m, c;
int ansq;
int ans_map[25][25];
int curq;
int cur_map[25][25];
int p[25]; inline void swp(int x1, int y1, int x2, int y2){
int t = cur_map[x1][y1];
cur_map[x1][y1] = cur_map[x2][y2];
cur_map[x2][y2] = t;
} inline int getQ(int x1, int y1, int x2, int y2){
int res = 0;
swp(x1, y1, x2, y2);
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j){
if (i < n)
if (cur_map[i][j] != cur_map[i+1][j])
++res;
if (j < m)
if (cur_map[i][j] != cur_map[i][j+1])
++res;
}
swp(x1, y1, x2, y2);
return res;
} void SA(){
register double temp = 10000.0;
int x1, y1, x2, y2;
int excq;
while (temp >= DEL){
x1 = (rand() % n) + 1, y1 = (rand() % m) + 1, x2 = (rand() % n) + 1, y2 = (rand() % m) + 1;
srand(rand());
excq = getQ(x1, y1, x2, y2);
if (excq < ansq){
curq = ansq = excq;
swp(x1, y1, x2, y2);
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j)
ans_map[i][j] = cur_map[i][j];
}
else if (exp(-(excq - ansq) / temp) * RAND_MAX > ((rand() % 1000000) / 1000000.0)){
curq = excq;
swp(x1, y1, x2, y2);
}
else{
if (curq - ansq >= (temp * 90)){
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j)
cur_map[i][j] = ans_map[i][j];
curq = ansq; } }
temp *= DELTA;
}
} int main(){
srand(19260817);
srand(rand()); srand(rand()); srand(rand());
n = read(), m = read(), c = read();
for (ri i = 1; i <= c; ++i)
p[i] = read();
int k1 = 1, k2 = 1;
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j){
ans_map[i][j] = cur_map[i][j] = k1;
++k2;
if (k2 > p[k1]){
++k1;
k2 = 1;
}
}
ansq = 0;
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j){
if (i < n)
if (cur_map[i][j] != cur_map[i+1][j])
++ansq;
if (j < m)
if (cur_map[i][j] != cur_map[i][j+1])
++ansq;
}
SA();
for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= m; ++j){
printf("%d", ans_map[i][j]);
if (j < m)
printf(" ");
else
printf("\n");
}
return 0;
}