気持ちとしては「swapの操作で位置合わせするのが本質なので、順列全探索 \(O(N! \ {\rm poly}(N))\) を bitDPで \(O(2^N{\rm poly}(N))\) に落とすいつものやつ」です。

より基本的な例題： ABC199E『Permutation』、 ABC180E『Traveling Salesman among Aerial Cities』

入れ替えの操作により \(A_i\) が \(A_{\sigma(i)}\) に移ったとします。\(\sigma\) を固定した時のトータルの操作コストを求めることは容易です。この \(\sigma\) を全探索することを考えます。

\(S\) を\(\{1,\ldots,N\}\) の部分集合として、\(DP[i][S]\) を 「\(\sigma(S)=\{1,\ldots,i\}\) であるような全ての \(\sigma\) についての、\(B_1,\ldots,B_i\) を一致させるまでに必要なコストの最小値」とします。

遷移としては、次に \(\sigma(k)=i+1\) となる \(k\) を決めることになるので、各 \(k\not \in S\) に対して、\(dp[i+1][S\cup\{k\}]\) に遷移することになります。

ここで、この時点での \(i\) 番目より後ろのindexの並び順は、\(\{1,\ldots,N\}\setminus S\) が昇順になっているので \(\sigma(k)=i+1\) とするために必要なswapの回数は \(j\not\in S\) かつ \(j<k\) をみたすような \(j\) の個数に等しくなります。これは愚直にやって \(O(N)\) 、ないし、bit演算により(適当な仮定のもとで) \(O(1)\) でできます。

\(i\neq |S|\) のケースを考慮する必要は無いことから、dpのキーに \(i\) は不要です。したがって以上により、状態数が \(O(2^N)\)、各状態からの遷移先が \(O(N)\)、遷移が \(O(1)\) なので、全体で \(O(N2^N)\) のDPにより解けました。

実装例(C)

実装例(Python)

def popcount(n):return bin(n).count("1")

N,X,Y=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
dp=[10**18]*(1<<N)
dp[0]=0

for s in range(1<<N):
  i=popcount(s)
  for k in range(N):
    # A[k]をiの位置に持っていく
    if (s>>k)&1:continue
    cnt=popcount((~s)&((1<<k)-1))  # 1からnのうち、sに入っておらず、kより小さいものの個数
    dp[s^(1<<k)]=min(dp[s^(1<<k)],dp[s]+abs(A[k]-B[i])*X+cnt*Y)

print(dp[(1<<N)-1])