1

我正在重新尝试这个问题陈述，现在比赛已经结束（所以它不是作弊或任何东西，只是想学习，因为没有公布答案，只有给定测试用例输入文件的正确输出）。

有 10 个给定的测试用例输入，要提交相关的输出文件。我最初的提交是一个朴素的嵌套 for 循环 (start,end) 对的实现，回答了以下问题：从 (0-based) index开始，到(inclusive)start结束的子字符串的波动性度量是什么。end

显然，对于 10 6的最大问题限制，O(N 2 ) 是不可行的，所以我只得到了正确的 5/10 测试用例（当然，第一个 - 也是更简单的 - 5）。

因此，我在这里写信是为了寻求关于如何改进我的算法的人群情报，即我怀疑嵌套的 for 循环（开始，结束）是优化的主要瓶颈（当然！）到目前为止，我'已经沿着尝试将其表述为字符串/子字符串问题的动态规划（DP）的路线，但在提出状态表示和转换位以便可以实现DP方面没有任何成功。

为了便于参考，并表明这不是家庭作业，我已经诚实地尝试过，我的原始提交可在此处找到。

非常感谢任何帮助，甚至是类似问题的链接，我可以通过谷歌搜索教程博客文章/示例解决方案/赛后编辑分析。

4

1 回答 1

0

你试过分而治之吗？

如果我正确理解了这个问题，给定一个长度为 n 的 DNA 链 S，我们将 S 分成两半，S_left 和 S_right，其中 S_left 由 S[i] 组成，其中 0 <= i < n/2，S_right 由 S [j] 其中 (n/2)+1 <= j < n。最不稳定的片段要么完全出现在 S_left 内，要么完全出现在 S_right 内，要么跨越 S_left 和 S_right 的边界。

为了找到 S_left 和 S_right 最易变的片段，我们只需使用递归。棘手的一点是找到跨越 S_left 和 S_right 边界的片段的波动性度量。这里有一个正整数分数的数学性质：给定四个正（非零）整数 a、b、c 和 d，(a + c) / (b + d) 永远不会大于 (a / b) 和(c/d)。这里a和b是 S_left 从边界开始的嘌呤和嘧啶的累积计数，而c和d是从边界开始的 S_right 中嘌呤和嘧啶的累积计数。这个数学性质意味着我们不需要检查超出 a = 0 或 c = 0 的交叉片段的波动率度量，因为它保证小于 S_left 或 S_right 的最大波动率。对于交叉片段，这种搜索的时间复杂度可以在 O(n) 中完成，对于整个算法，可以在 O(n lg n) 中完成。

希望这有效，因为我没有编写算法。也许它有一个 O(n) 时间的 DP 算法来解决这个问题，但这就是我现在所拥有的。

于 2013-10-24T15:43:49.530 回答