2

我有一个需要编写的程序，但我不知道该怎么做。我需要参考如何解决它的方法。问题如下：
您有一个包含N个整数的列表。例如：[4;2;3;2;1;5;1;3;2]。
如果有一些K或更多数量的相邻重复数字，则将它们从列表中删除。您可以在任何两个数字之间添加任何数字，或添加到列表的开头/结尾，以便从列表中删除数字。

任务是使用尽可能少的数字来清除列表。

1 <= N <= 100 - N是列表的长度。
2 <= K <= 5 - K是从序列中删除的重复相邻数字的最小数量。

K在指定的范围内提供。

示例：List = [4;2;3;2;1;5;1;3;2] - 答案是3；K = 2

我的想法是有某种序列树，以便有效地删除数字。此示例的树如下所示：

4 2       2
   3     3
    2 1 1
       5

所以你必须在列表的第 4 和第 5 个元素之间添加5（从 0 开始），然后第 4 到第 7 个元素消失，序列看起来像这样。

4 2   2
   3 3
    2

现在您在新序列的第 2 和第 3 个元素之间添加2，因此第 1 到第 5 个元素被删除。

然后将 4 添加到新序列中，添加到序列中的数字总数为3。这个问题的算法是什么？谢谢。

4

1 回答 1

0

让我们对问题进行逆向工程。考虑到您的示例，可以在运行中减少的最终字符串将如下所示

4           4
 2         2
  3       3
   2     2
    1   1
     5 5

如果你注意到它是一个偶数长度的回文。对于所有其他可能的输入，情况也是如此。

现在问题可以归结为找到输入中最长的回文子序列，并将一个字符添加到输入字符串中，该字符对应于输入中不在回文子序列中的每个字符。寻找最长的回文子序列是一个标准的 DP 问题，教程可以在这里找到

例如，在您的情况下，最长的子序列将是[2,3,1,1,3,2]并且不在输入中的字符是，[4,2,5]因此您必须将这些添加到输入中，或者如果您对数字感兴趣，那么3答案就是答案。

于 2012-10-26T12:28:51.597 回答