AtCoder Beginner Contest 232 F

https://atcoder.jp/contests/abc232/tasks/abc232_f

解説を見てもよくわからなかったので、「bitDP 順列」で検索してみると、

https://qiita.com/masayoshi361/items/0be4bce77783b6013b34

ここのコードを読んだらわかりました。要は、順列を集合に圧縮するわけですね。順列1 2と2 1は共に集合{1, 2}と考えて、本問ならコストが小さい方をdp[{1, 2}]とすればよいわけです。
隣同士の互換の回数ですが、例えば123を321するには、3を1番前に移動するには2回、この時点で312、2を2番目にするには1回の合計3回かかります。
この計算にひと工夫が必要です。例えば、N=5でdp[{2,3,4}]を考えましょう。4を{2,3}の次の順列にするには、4番目から3番目に移動するから1回の互換が必要です。次に、3を{2,4}の次の順列にするには、今{2,4}135になっているから、4番目から3番目に移動するから1回の互換が必要です。最初は3番目にあったけど、4が3より大きいから4番目に移動しているわけですね。次に、2を{3,4}の次に順列にするには、今{3,4}125になっているから、4番目から3番目に移動するから1回の互換が必要です。最初は2番目にあったけど、3,4が2より大きいから4番目に移動しています。
まとめると、{2,3,4}の中で大きい方から処理していって、n-3+counter回互換します。counterは前の順列の中で自分より大きい数の個数です。counterは0から処理するごとにインクリメントします。

# coding: utf-8
# Simple Operations on Sequence

from itertools import *
import sys

sys.setrecursionlimit(2*10**5)


#################### library ####################

def read_tuple():
    return tuple(map(int, raw_input().split()))

def read_list():
    return list(map(int, raw_input().split()))


#################### naive ####################

def F_naive(X, Y, A, B):
    def num_swaps(v):
        n = 0
        for i in range(N-1):
            n += v[i] - i + sum(1 for j in range(i) if v[j] > v[i])
        return n
    
    def cost(v):
        return X * sum(abs(B[v[i]] - A[i]) for i in range(N)) + Y * num_swaps(v)
    
    N = len(A)
    return min(cost(v) for v in permutations(range(N)))


#################### process ####################

def read_input():
    N, X, Y = read_tuple()
    A = read_list()
    B = read_list()
    return (X, Y, A, B)

def F(X, Y, A, B):
    N = len(A)
    dp = [0] * (1 << N)
    dp[0] = 0
    for n in range(1, (1<<N)):
        v = []
        k = sum(1 for j in range(N) if (n >> j) & 1) - 1
        counter = 0
        for i in range(N-1, -1, -1):
            if (n >> i) & 1:
                v.append(dp[n-(1<<i)] + X * abs(A[k] - B[i]) + Y * counter)
                counter += 1
        dp[n] = min(v)
    return dp[-1]


#################### main ####################

X, Y, A, B = read_input()
#print F_naive(X, Y, A, B)
print F(X, Y, A, B)