传送门

题意是说给一个网格，每个格子有一个权值，选择其中一些格子涂黑，要求黑色直接不能临边。然后还需要找到一条哈密顿回路。

问如何选择黑色的格子使得权值最大。

插头DP，0表示无插头，1、2表示对应联通分量的插头，3表示黑色格子的插头。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 100007;
int n;
int a[16][16], state[2][N], dp[2][N], now;
int G(int k, int x) {return (k >> (x << 1)) & 3;} // 轮廓线k的第x位状态
int F(int k, int x) {return k << (x << 1);} // 编码第x位的状态k
// unordered_map<int, int> st;
int fst[N], pre[N], mk[N], mt, tot;
void init()
{
    mt++; tot = 0;
}
void insert(int s, int w)
{
    int sp = s % N;
    if(mk[sp] != mt) mk[sp] = mt, fst[sp] = -1;
    for(int i = fst[sp]; ~i; i = pre[i])
    {
        if(state[now][i] == s) 
        {
            dp[now][i] = max(dp[now][i], w);
            return ;
        }
    }
    state[now][tot] = s;
    dp[now][tot] = w;
    pre[tot] = fst[sp]; fst[sp] = tot++;
}
int ans = 0;
void solve(int i, int j)
{
    int t = max(1, tot);
    init();
    for(int k = 0; k < t; k++)
    {
        int s = state[1 - now][k];
        int val = dp[1 - now][k];
        int p = G(s, j - 1), q = G(s, j);
        // 原状态s[i] xor 新状态 c ^ (s[i]) = c 
        if(p == 0 && q == 0) insert(s ^ F(3, j - 1) ^ F(3, j), val + a[i][j]); // 情况1 新建联通分量
        if((p == 0 || p == 3) && (q == 0 || q == 3)) // 情况3 保持原有联通分量
        {
            if(i + 1 <= n && j + 1 <= n) insert(s ^ F(1 ^ p, j - 1) ^ F(2 ^ q, j), val);
        } 
        else if(p == 0 || p == 3)
        {
            if(j + 1 <= n) insert(s ^ F(p, j - 1), val);
            if(i + 1 <= n) insert(s ^ F(p ^ q, j - 1) ^ F(q, j), val);
        }
        else if(q == 0 || q == 3)
        {
            if(i + 1 <= n) insert(s ^ F(q, j), val);
            if(j + 1 <= n) insert(s ^ F(q ^ p, j) ^ F(p, j - 1), val);
        }
        else if(p == 1 && q == 1) // 情况2 合并联通分量
        {
            int tmp = 1;
            for(int l = j + 1; l <= n; l++)
            {
                if(G(s, l) == 1) tmp++; else if(G(s, l) == 2) tmp--;
                if(tmp == 0) {insert(s ^ F(p, j - 1) ^ F(q, j) ^ F(2 ^ 1, l), val); break;}
            }
        }
        else if(p == 2 && q == 2)
        {
            int tmp = 1;
            for(int l = j - 2; l > 0; l--)
            {
                if(G(s, l) == 1) tmp--; else if(G(s, l) == 2) tmp++;
                if(tmp == 0) {insert(s ^ F(p, j - 1) ^ F(q, j) ^ F(1 ^ 2, l), val); break;}
            }
        }
        else if(p == 2 && q == 1)
        {
            insert(s ^ F(p, j - 1) ^ F(q, j), val);
        }
        else 
        {
            if(i == n && j == n) ans = max(ans, val);
            if(i == n && j == n - 1 && G(s, n) == 0) ans = max(ans, val + a[n][n]);
        }
    }
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // time_t startt = clock();

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int cas; cin >> cas;
    while(cas--)
    {
        cin >> n;
        ans = 0; now = 0; state[0][0] = 0; dp[0][0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) cin >> a[i][j];

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                now = 1 - now;
                memset(state[now], 0, sizeof state[now]);
                memset(dp[now], 0, sizeof dp[now]);
                solve(i, j);
            }
            for(int k = 0; k < tot; k++) 
            {
                state[now][k] <<= 2; 
                state[now][k]&=(F(1,n+1)-1); // 删掉第n+1位，使得维护的Hash表状态有效
            }
        }
        cout << ans << endl;
    }    
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}