java - 竞争性编码 - 以最低成本清除所有级别 : Not passing all test cases

Question

当我遇到这个问题时，我正在一个竞争性编码网站上解决问题。问题指出:
在这个游戏中有N个级别和M种可用的武器。级别从 0 到 N-1 编号，武器从 0 到 M-1 编号。 您可以按任意顺序通关。在每个关卡中，通关都需要这些 M 武器的某些子集。如果在特定级别，您需要购买 x 件新武器，您将为此支付 x^2 个硬币。另请注意，您可以将当前拥有的所有武器带到下一个级别。最初，你没有武器。你能找出通关所有关卡所需的最低硬币数吗？

输入格式 输入的第一行包含 2 个空格分隔的整数: N = 游戏中的关卡数 M = 武器种类数

接下来是 N 行。这些行的第 i 个包含长度为 M 的二进制字符串。如果第 j 个字符 这个字符串是 1 ，这意味着我们需要一个 j 类型的武器来通关第 i 个级别。

约束 1 <= ñ <= 20 1<= 米 <= 20

输出格式 打印一个整数作为问题的答案。

示例测试用例 1
输入
1 4
0101

输出
4

解释 这个游戏只有一个级别。我们需要两种类型的武器 - 1 和 3。因为，最初 Ben 没有武器，他将不得不购买这些武器，这将花费他 2^2 = 4 个硬币。

示例测试用例 2
输入
3 3
111
001
010

输出
3

解释 这场比赛有3个级别。第 0 级 (111) 需要所有 3 种类型的武器。第 1 级 (001) 只需要类型 2 的武器。第 2 级只需要类型 1 的武器。如果我们按给定顺序 (0-1-2) 通关，则总成本 = 3^2 + 0^2 + 0^2 = 9 个硬币。如果我们按照1-2-0的顺序通关，那么花费= 1^2 + 1^2 + 1^2 = 3个硬币，这是最优的方式。

方法
我能够弄清楚，我们可以通过遍历二进制字符串的方式计算出最低成本，即我们在每个级别购买尽可能少的武器。

一种可能的方法是遍历二进制字符串数组并在数组已按正确顺序排列时计算每个级别的成本。正确的顺序应该是当字符串已经排序时，即 001、010、111，如上述测试用例的情况。按此顺序遍历数组并将每个级别的成本相加给出正确答案。

此外，java 中的 sort 方法可以很好地对这些二进制字符串进行排序，然后在数组上运行循环以汇总每个级别的成本。

Arrays.sort(weapons);

这种方法适用于一些测试用例，但是超过一半的测试用例仍然失败，我不明白我的逻辑有什么问题。我正在使用按位运算符来计算每个级别所需的武器数量并返回它们的方 block 。

不幸的是，我看不到失败的测试用例。非常感谢任何帮助。

Answer 1

这可以通过动态规划来解决。

状态将是我们当前拥有的武器的位掩码。

转换将尝试清除每个 n从当前状态依次可能达到的水平，获取我们需要的额外武器并支付费用。 在每个n结果状态，我们采用当前方法和所有先前观察到的方法的最小成本来实现它。 当我们已经拥有一些武器时，有些关卡实际上不需要购买额外的武器；这种转换将自动被忽略，因为在这种情况下，我们到达相同的状态并支付相同的成本。

我们从 m 的状态开始零，已付款 0 . 最终状态是所有给定级别的按位或，到达那里的最低成本就是答案。

在伪代码中:

let mask[1], mask[2], ..., mask[n] be the given bit masks of the n levels
p2m = 2 to the power of m
f[0] = 0
all f[1], f[2], ..., f[p2m-1] = infinity
for state = 0, 1, 2, ..., p2m-1:
    current_cost = f[state]
    current_ones = popcount(state)  // popcount is the number of 1 bits
    for level = 1, 2, ..., n:
        new_state = state | mask[level]  // the operation is bitwise OR
        new_cost = current_cost + square (popcount(new_state) - current_ones)
        f[new_state] = min (f[new_state], new_cost)
mask_total = mask[1] | mask[2] | ... | mask[n]
the answer is f[mask_total]

复杂度为O(2^m * n)时间和O(2^m)内存，这对 m <= 20 应该没问题和 n <= 20在大多数在线评委中。