题意：
求把数组 a[] 变成 b[] 的最小花费。有两种操作：
- 花费 \(X\) 把任一元素 \(+1/-1\)
- 花费 \(Y\) 交换相邻的两个数
\(n\le 18\)
思路：
很帅的状压dp！
看到 \(n\le 18\)，就很想状压！但怎么表示状态呢？排列数是阶乘级别的，怎样才能 \(O(n2^n)\) 呢？
考虑先进行所有的交换操作，再进行所有的加减操作。设进行完所有的交换操作后得到的 “理想排列” 为 A[]，我们把 A[] 中的元素重新标号为 \(1,\cdots , n\)，那么从 a[] 变到 A[] 需要的交换次数就等于 a[] 相对于 A[] 的逆序数
怎么数逆序数？先看标号为 \(1\) 元素后面比它标号小的数的个数，再看 \(2\) 的后面比它小的数的个数，以此类推。（也可以看前面比它大的数的个数，写法类似）
然而理想排列 A[] 是未知的，因此每个元素在 A[] 中的标号也未知，咋办？设 \(f_S\) 为把 a[] 中 \(S\) 表示的位置上的那些元素变换到 A[] 中前 \(|S|\) 个位置的最小花费。这样我们仅仅知道 \(S\) 包含哪些位置，而完全不知道这些 a[] 中的每个元素变换到了 A[] 中的具体哪个位置。现在我们要将 \(i\notin S\) 加入，那么 \(S\) 正是所有 “在 A[] 中的标号比 a[i] 在 A[] 中的标号小的元素” 在 a[] 中的位置。
const int N = 18;
ll n, X, Y, a[N], b[N], f[1<<N];
void sol() {
cin >> n >> X >> Y;
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] = 0;
for(int S = 0; S < (1<<n); S++)
for(int x = 0; x < n; x++)
if(!(S >> x & 1)) {
int invCnt = 0; for(int i = x + 1; i < n; i++)
if(S >> i & 1) invCnt++;
f[S | (1<<x)] = min(f[S | (1<<x)],
f[S] + Y * invCnt + X * abs(a[x] - b[__builtin_popcount(S)]) );
}
cout << f[(1<<n) - 1];
}