swap たち全て \(\rightarrow\) abs たち全て
の順で操作をしても良い．
まず \(n\) 次 permutation \(P\) を固定して， \(P\) に対するコストを求める．
- Swap of \(P\) の回数は，転倒数で求まる． これに \(y\) を掛けると，swap に対するコストになる．
- abs のコストは，各 \(i \in n\) に対して \(abs(a_{P{i}} - b_{i})\) の和に \(x\) を掛ければよい． つまり， \(\sum_{i \in n} (abs(a_{P{i}} - b_{i})) x \) となる．
これを全探索で求める． 転倒数を求める方を軸に考えたいので，転倒数を求める手順を参考にする． \(P_{[0,i)}\) の行き先が決まっているとして，それを \(s \in 2^{n}\) とおく．\(s\) は \(\vert s \vert = i\) であることが，\(P\) の正しい取り方と必要十分． つまり \(Im(P_{[0,i)}) = s\). このとき，\(P\) による \(i\) の行き先を決めたいので，それを \(ne \in n\) とする．
コストを度外視すると，\(ne \not\in s\) が \(P_{i} = ne\) とできる必要十分． このときのコストは，\(i\)-th inversion と \(i\)-th abs を求めれば確定する．
\(i\)-th inv: \(s\) の元のうち，\(P_{i}\) よりも大きいものの個数
\(i\)-th abs: \(abs(b_{i} - a_{P_{i}})\) となる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,x,y;
cin >> n >> x >> y;
vll a(n); cinv(a);
vll b(n); cinv(b);
vll dp(1LL<<n, INFL);
dp[0] = 0;
rep(i,n) rep(s,1LL<<n) if(pcntll(s) == i){
rep(ne,n) if(!(s >> ne & 1)){
ll t = s | (1LL << ne);
ll inv = pcntll(s >> ne);
ll ab = abs(b[i] - a[ne]);
chmin(dp[t], dp[s] + inv*y + ab*x);
}
}
cout << dp.back() << endl;
return 0;
}
