请注意，由于A[i] A[i]的每个子集，并且可以在任何时间限制内轻松适应。

让M为唯一的A[i]的数量，然后有一个O(NM + M * 2^M)动态编程解决方案，带有位掩码。

请注意，当我说移动A[i]时，是指移动每个值为A[i]的元素

要了解我们如何做到这一点，我们首先考虑一下蛮力解决方案。我们将一组唯一的A[i]移到字符串的开头，然后在每一步中，选择下一个A[i]移到原始位置之后。这是O(M! * N)。

这里有一个重要的发现：如果我们在字符串的开头有一组A[i]，然后我们移动下一组，即原始A[i]的顺序其实并不重要。无论顺序如何，任何移动都将花费相同的费用。

让cost(subset,A[i])成为将所有A[i]移动到字符串前面A[i]的那个子集之后的代价。然后我们可以编写以下代码：

dp = [float('inf')] * (1 << M) # every subset of A[i]
dp[0] = 0
for mask in range(len(dp)):
    for bit in range(M):
        # if this A[i] hasn't been moved to the front,we move it to the front
        if (mask >> bit) & 1 == 0: 
            dp[mask^(1 << bit)] = min(dp[mask^(1 << bit)],dp[mask] + cost(mask,bit))

如果我们天真地计算cost，那么我们就有O(M * 2^M * N)。但是，我们可以使用每个值cost来预先计算O(1)的每个值。

这是我们可以做到的：

想法：对数组进行排序所需的交换次数为反转次数。

让我们定义一个新数组inversions[M][M]，其中inversions[i][j]是j在i中位于arr之后的次数。为了清楚起见，这是我们如何天真地计算它：

for i in range(len(arr)):
    for j in range(i + 1,len(arr)):
        if arr[i] != arr[j]: inversions[arr[i]][arr[j]] += 1

假设我们有inversions，那么我们可以像这样计算cost(subset,A[i])：

cost = 0
for bit in range(M):
    # if bit isn't in the mask and thus needs to get swapped with A[i]
    if (subset >> bit) & 1 == 0:
        cost += inversions[bit][A[i]]

剩下的是：

1. 计算inversions中的O(NM)。这可以通过在M中的每个索引处保留每个N的计数来完成。

2. 当前cost是O(M)，而不是O(1)。我们可以在cost上运行单独的动态编程以构建数组cost[(1 << M)][M]，其中cost[i][j]是将项目j移动到子集i的成本。

出于完整性考虑，here是用C ++编写的完整代码。这是我对代码强制问题的意见。请注意，在该代码中，cost被命名为contribution。