[JLOI2009]神秘的生物
只需要维护连通情况,采用最小表示法,表示此格是否存在,也即插头是否存在
分情况讨论当前格子的轮廓线上方格子和左方格子状态,转移考虑当前格子选不选,决策后状态最后要能合法
\(\text{Code}\)
$\text{Code}$
#include <bits/stdc++.h>
#define IN inline
using namespace std;
const int N = 15;
int bit[N], a[N][N], ans = -2e9, n;
struct Hash_Table {
#define mod 590027
struct edge{int nxt, sta, f;}e[1 << 24];
int h[mod + 5], tot;
IN void clear(){tot = 0, memset(h, 0, sizeof h);}
IN void insert(int s, int v) {
int id = s % mod;
for(int i = h[id], x; i; i = e[i].nxt)
if (e[i].sta == s) return e[i].f = max(e[i].f, v), void();
e[++tot] = edge{h[id], s, v}, h[id] = tot;
}
}hs[2];
IN int Recode(int s, int v) {
int vis[8] = {}, cnt = 0, t = 0;
for(int i = 0, x; i < n; i++) {
if (!(x = (s >> 3*i) & 7)) continue;
if (!vis[x]) vis[x] = ++cnt;
t += vis[x] * bit[i];
}
if (cnt == 1) ans = max(ans, v);
return t;
}
IN int Count(int s, int v) {
int res = 0;
for(int i = 0; i < n; i++) if (((s >> 3*i) & 7) == v) ++res;
return res;
}
void solve() {
int cur = 0; hs[cur].insert(0, 0);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
hs[cur^1].clear();
for(int k = 1; k <= hs[cur].tot; k++) {
int curS = hs[cur].e[k].sta, curF = hs[cur].e[k].f;
int bd = (curS >> 3*(j - 1)) & 7, br = 0;
if (j > 1) br = (curS >> 3*(j - 2)) & 7;
if (!bd && !br) {
hs[cur^1].insert(Recode(curS, curF), curF);
hs[cur^1].insert(Recode(curS + 7*bit[j-1], curF + a[i][j]), curF + a[i][j]);
}
else if (!bd && br) {
hs[cur^1].insert(Recode(curS, curF), curF);
hs[cur^1].insert(Recode(curS + br*bit[j-1], curF + a[i][j]), curF + a[i][j]);
}
else if (bd && !br) {
hs[cur^1].insert(Recode(curS, curF + a[i][j]), curF + a[i][j]);
if (Count(curS, bd) >= 2) hs[cur^1].insert(Recode(curS - bd*bit[j-1], curF), curF);
}
else {
if (Count(curS, bd) >= 2) hs[cur^1].insert(Recode(curS - bd*bit[j-1], curF), curF);
if (br != bd) for(int w = 0; w < n; w++) if (((curS >> 3*w) & 7) == bd) curS += bit[w] * (br - bd);
hs[cur^1].insert(Recode(curS, curF + a[i][j]), curF + a[i][j]);
}
}
cur ^= 1;
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]), ans = max(ans, a[i][j]);
bit[0] = 1;
for(int i = 1; i <= n; i++) bit[i] = bit[i - 1] << 3;
solve(), printf("%d\n", ans);
}