题解：P11934 [CrCPC 2024] 排序

ELECTRODE_kaf · 2025-03-29 21:51:28 · 题解

暴力枚举三个分割点跑 DFS 即可，考虑剪枝：定义两个衡量操作价值的数：v_1=\sum [a_i=a_{i+1}],v_2=\sum[a_i>a_{i+1}]。显然 v_1 应该尽量大，v_2 应该尽量小。用这两个标准比对修改前后的序列剪枝。

const ll N = 20, MAX = 6;
ll n, a[N], ans = MAX, goal;
map<ll, bool> vis;
map<ll, ll> mem;

ll hash1() {
    ll ret = 0;

    rep(i, 1, n) ret = ret * 10 + a[i] - 1;

    return ret;
}

void dfs(ll step) {
//  cout << "dfs:step=" << step << ",status=";
//
//  rep(i, 1, n) cout << a[i] << ' ';
//
//  endl;
//  pause;
    ll tmp = hash1();
//  cout << "tmp=" << tmp << '\n';
//  pause;

    if ((vis[tmp] and mem[tmp] <= step) or step >= ans)
        return;

//  cout << "signal!\n";
    vis[tmp] = 1;
    mem[tmp] = step;

    if (tmp == goal) {
        update(ans, step, min);
        return;
    }

    ll v11 = 0, v12 = 0;

    rep(i, 1, n - 1) {
        if (a[i] + 1 == a[i + 1])
            v11++;
        else if (a[i] > a[i + 1])
            v12++;
    }

    rep(i, 0, n) {
        rep(j, i, n) {
            rep(k, j, n) {
//              cout << "status=";
//
//              rep(i, 1, n) cout << a[i] << ' ';
//
//              endl;
//              pause;
//              cout << i << ' ' << j << ' ' << k << '\n';
//              pause;
                vector<ll> new1;
                new1.clear();

                rep(l, j + 1, k) new1.pb(a[l]);

                rep(l, 1, i) new1.pb(a[l]);

                rep(l, k + 1, n) new1.pb(a[l]);

                rep(l, i + 1, j) new1.pb(a[l]);

//              cout << "size:" << new1.size() << '\n';
//              pause;

//              for (ll l : new1)
//                  cout << l << ' ';
//
//              endl;
//              pause;
                ll v21 = 0, v22 = 0;

                rep(l, 0, n - 2) {
                    if (new1[l] + 1 == new1[l + 1])
                        v21++;
                    else if (new1[l] > new1[l + 1])
                        v22++;
                }

//              cout << "v11=" << v11 << ",v12=" << v12 << ",v21=" << v21 << ",v22=" << v22 << '\n';
//              pause;

                if (v11 >= v21 or v22 > v12)
                    ctn;

//              cout << "signal A\n";
                ll _a[N];
                cpy(_a, a);

                rep(i, 1, n) a[i] = new1[i - 1];

                dfs(step + 1);
                cpy(a, _a);
            }
        }
    }
}

int main() {
    cin >> n;

    rep(i, 1, n) cin >> a[i];

    rep(i, 0, n - 1) goal = goal * 10 + i;

//  cout << "goal=" << goal << '\n';
//  pause;
    dfs(0);

    cout << ans;
}