安排范围 a (n) (a [i] <= 20) 使得相等的值将形成连续的段的最小成本是多少？

Question

您提供了 1 个字符串：a1, a2..an (a [i] <= 20)

要求：交换序列中任意两个元素使得最终得到的序列具有相等值且连续的最小代价（步数）：

每一步只能选择2个相邻的值交换：swap(a[i],a[i+1])=1steps

示例：

1 1 3 1 3 2 3 2

Swap (a [3], a [4])

Swap (a [6], a [7])

-> 1 1 1 3 3 3 2 2

minimum = 2

我需要你的帮助。

Answer 1

请注意，由于 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]，然后我们移动下一个，即我们原来的一组 [=13] 的顺序=] 实际上并不重要。无论顺序如何，任何移动都将花费相同的费用。

设 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]是arr中i之后j出现的次数。为了清楚起见，我们将如何天真地计算它：

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]]

剩下的是：

在 O(NM) 中计算 inversions。这可以通过在 N.

M

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

为了完整性 here 是用 C++ 编写的完整代码。这是我在 codeforces 上提交的相同问题。请注意，在该代码中 cost 被命名为 contribution。

安排范围 a (n) (a [i] <= 20) 使得相等的值将形成连续的段的最小成本是多少？

What is the minimum cost of arranging the range a (n) (a [i] <= 20) such that the equal values will form a continuous segment?

algorithm

sorting

greedy