algorithm - 创建交替链的最少切换

Question

我正在尝试在 SPOJ 上解决此问题:http://www.spoj.pl/problems/EDIT/

我试图获得该算法的一个像样的递归描述，但我失败了，因为我的想法一直在原地打转!你们能帮我解决这个问题吗？我将尝试描述我正在尝试解决此问题的方法。

基本上我想解决大小为 j-i 的问题，其中 i 是起始索引，j 是结束索引。现在，应该有两种情况。如果 j-i 是偶数，那么起始和结束字母必须是相同的大小写，而当 j-i 是奇数时，它们必须是相反的大小写。我也想减少较小尺寸(j-i-1或j-i-2)的问题，但我觉得如果我知道较小问题的解决方案，那么构建更大问题的解决方案还应该考虑到较小问题的起始和结束字母大小写。这正是我感到困惑的地方。你们能让我的想法走上正轨吗？

Answer 1

我认为递归不是解决这个问题的最佳方法。如果我们采取不同的方法，这个问题可以很快解决!

让我们考虑一下二进制字符串。假设大写字符为 1，小写字符为 0。例如

AaAaB -> 10101
ABaa  -> 1100
a     -> 0

“正确的”交替链是 10101010.. 或 010101010..

我们将一个字符串更改为另一个字符串所需的最小替换次数称为 Hamming distance 字符串之间。我们要找到的是输入二进制字符串与相同长度的两个交替链之一之间的最小汉明距离。

这并不难:我们对每个字符串进行异或，然后计算 1 的数量。 (link)。例如，让我们考虑以下字符串:ABaa。

• 我们将其转换为二进制:

  阿巴 -> 1100

• 我们生成仅有的两条长度为 4 的交替链:

  1010

  0101

• 我们将它们与输入进行异或:

  1100 异或 1010 = 0101

  1100 异或 0101 = 1010

• 我们计算结果中的 1 并取最小值。在本例中，它是2。

我用 Java 编写了这个过程，并进行了一些小的优化(缓冲 I/O，不需要生成交替链)，并且它被接受了:(0.60 秒一个)。