问将范围a (n) (a [i] <= 20)安排成一个连续段的最小成本是多少？

EN

请注意，自A[i] <= 20以来，我们可以继续枚举所有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在arr中i之后的次数。为了清晰起见，我们将天真地计算它：

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]是将item j移动到子集i的成本。

为了完整起见，这里是用C++编写的完整代码。这是我针对同样的代码强制问题提交的报告。注意，在该代码中，cost被命名为contribution。