T0803 交换

#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);
int n;
vector<vector<long long>> c;

// 子树区间 [lo,hi] 的 DP 矩阵。
// d[i*len+j]：把这棵子树的叶子排成一列，第一个叶子是自然序第 i 个、
// 最后一个是自然序第 j 个时，子树内部的最小总权值。
struct Mat {
    int lo, len;
    vector<long long> d;
    long long &at(int i, int j) { return d[(size_t)i * len + j]; }
    long long at(int i, int j) const { return d[(size_t)i * len + j]; }
};

Mat solve(int lo, int hi) {
    Mat m;
    m.lo = lo;
    m.len = hi - lo + 1;
    if (m.len == 1) { m.d.assign(1, 0); return m; }

    int mid = (lo + hi) / 2;
    Mat A = solve(lo, mid);            // 左子树
    Mat B = solve(mid + 1, hi);        // 右子树
    int a = A.len, b = B.len;
    m.d.assign((size_t)m.len * m.len, INF);

    {   // 顺序：左子树在前
        vector<long long> H((size_t)a * b, INF);
        for (int jA = 0; jA < a; jA++) {
            const long long *crow = c[A.lo + jA].data() + B.lo;
            for (int j = 0; j < b; j++) {
                long long best = INF;
                for (int iB = 0; iB < b; iB++) {
                    best = min(best, crow[iB] + B.at(iB, j));
                }
                H[(size_t)jA * b + j] = best;
            }
        }
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                long long best = INF;
                for (int jA = 0; jA < a; jA++) {
                    best = min(best, A.at(i, jA) + H[(size_t)jA * b + j]);
                }
                m.at(i, a + j) = best;
            }
        }
    }
    {   // 顺序：右子树在前
        vector<long long> H((size_t)b * a, INF);
        for (int jB = 0; jB < b; jB++) {
            const long long *crow = c[B.lo + jB].data() + A.lo;
            for (int j = 0; j < a; j++) {
                long long best = INF;
                for (int iA = 0; iA < a; iA++) {
                    best = min(best, crow[iA] + A.at(iA, j));
                }
                H[(size_t)jB * a + j] = best;
            }
        }
        for (int i = 0; i < b; i++) {
            for (int j = 0; j < a; j++) {
                long long best = INF;
                for (int jB = 0; jB < b; jB++) {
                    best = min(best, B.at(i, jB) + H[(size_t)jB * a + j]);
                }
                m.at(a + i, j) = best;
            }
        }
    }
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    c.assign(n, vector<long long>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> c[i][j];

    if (n == 1) { cout << 0 << '\n'; return 0; }

    int mid = n / 2;
    Mat A = solve(0, mid - 1);
    Mat B = solve(mid, n - 1);

    // f[j]：子树里以第 j 个叶子结尾的最小代价；g[i]：以第 i 个叶子开头的最小代价
    vector<long long> fA(A.len, INF), gA(A.len, INF), fB(B.len, INF), gB(B.len, INF);
    for (int i = 0; i < A.len; i++)
        for (int j = 0; j < A.len; j++) {
            fA[j] = min(fA[j], A.at(i, j));
            gA[i] = min(gA[i], A.at(i, j));
        }
    for (int i = 0; i < B.len; i++)
        for (int j = 0; j < B.len; j++) {
            fB[j] = min(fB[j], B.at(i, j));
            gB[i] = min(gB[i], B.at(i, j));
        }

    // 根节点只需要全局最小值，不必算完整的矩阵
    long long ans = INF;
    for (int jA = 0; jA < A.len; jA++)
        for (int iB = 0; iB < B.len; iB++)
            ans = min(ans, fA[jA] + c[A.lo + jA][B.lo + iB] + gB[iB]);
    for (int jB = 0; jB < B.len; jB++)
        for (int iA = 0; iA < A.len; iA++)
            ans = min(ans, fB[jB] + c[B.lo + jB][A.lo + iA] + gA[iA]);

    cout << ans << '\n';
    return 0;
}