[ABC328G] Cut and Reorder 题解

状压fw实锤

思路

观察到排列操作只会做一次，答案的编号一定是一段一段的。

所以可以考虑 \(f_s\) 表示前 \(popcount(s) + 1\) 个 \(a\) 元素，放进 \(b\) 中 \(s\) 的最小代价

转移可以考虑放置一段，每放一段需要 \(c\) 的代价。

专业看起来复杂度非常爆炸，但是仔细分析可以得到时间复杂度为 \(O(2^nn)\)。

// Problem: [ABC328G] Cut and Reorder
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-03 13:29:14

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 22;

int n, c, f[(1 << N)], a[N], b[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> c;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];
    memset(f, 0x3f, sizeof f);
    f[0] = -c;
    for(int s = 0, now; s < (1 << n); s ++) {
        now = __builtin_popcount(s);
        for(int i = 0; i < n; i ++) {
            if(s >> i & 1) continue;
            int ss = s, sum = 0;
            for(int j = i; j < n; j ++) {
                if(s >> j & 1) break;
                ss |= (1 << j), sum += abs(a[now + j - i] - b[j]);
                f[ss] = min(f[ss], f[s] + sum + c);
            }
        }
    }
    cout << f[(1 << n) - 1] << '\n';

    return 0;
}