一个动态规划问题

Question

一个动态规划问题

8

请问有人能帮我找到一个最优的动态规划算法来解决这个问题吗？

在去晚餐的路上，CCC（加拿大计算机竞赛）的参赛者们排队等候他们美味的卷曲薯条。N（1≤N≤100）名参赛者单文件排队进入自助餐厅。

Doctor V是CCC的负责人，在最后一刻意识到程序员们简直讨厌站在使用不同语言的程序员旁边排队。值得庆幸的是，CCC只允许两种语言：Gnold和Helpfile。此外，参赛者们已经决定只有在至少有K（1≤K≤6）名参赛者组成的小组中才会进入自助餐厅。

Doctor V决定按照以下方案进行迭代：

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
* The remaining competitors will close the gap, potentially putting similar-language competitors together.

医生V已经为您记录了参赛选手的序列。所有的选手都能用餐吗？如果可以，需要发送多少个最小组参加晚宴？

输入：

第一行包含两个整数N和K。第二行包含N个字符，这些字符是排队的竞争者的序列（H代表Helpfile，G代表Gnold）。

输出：

在一行上输出一个数字，即形成晚宴所需的最小分组数量。如果不能让所有程序员用餐，则输出-1。

- GEP

2

如果你想得到一些答案，最好适当地标记问题。"trick"是一个非常没有意义的标签。 - Felix Kling

@kletoskletos - 这里使用动态规划的原因是什么？由于我们已经知道了Helpfile程序员和Gnold程序员的数量，我们可以将它们的数量除以Doctor V指定的组数。任何一组中剩余的程序员都需要添加到已经形成的组中，以避免超过六个人的组。我猜这就是动态规划发挥作用的地方。有趣的问题。 - sc_ray

@sc_ray：我认为你误读了问题。你需要找到至少K个人的连续组，并将他们从队列中移除，以便最终可以将所有人从队列中移除。你不能重新排列队列，只能移除相邻的志同道合的程序员组。 - Null Set

@Null Set：在这种情况下，如果K>=2，您将如何对以下序列GHHGHHGH进行分组？ - sc_ray

@sc_ray - 你不会这样做，你应该打印-1。 - IVlad

所以基本上问题归结为找到具有共同字符的最长子字符串，但对于像GHHGHHG这样的序列，其中G是孤立的，我们需要找到所有的G，直到达到组限制？ - sc_ray

3个回答

0

子问题是在给定排队状态下，需要最少的组来让每个人用餐。有很多可能的排队状态，但只有几种实际上会被看到，因此您的记忆化应该使用哈希映射来完成。

以下是一些伪代码。

int dine(string line){
    if(hashmap.contains(line)){
        return hashmap.get(line);
    }
    if(line.length == 0){
        return 0;
    }
    best = N+1;
    for(i=0;i<line.length;i=j){
        type = string[i];
        j = i+1;
        while(type == string[j]){
            j++;
        }
        if(j-i >= K){
             result = dine(string.substring(0,i-1) + string.substring(j,string.length));
             if(result > 0 && result < best){
                  best = result;
             }
        }
    }
    if(best == N+1){
         hashmap.insert(line, -1);
         return -1;
    }
    else {
         hashmap.insert(line, best+1);
         return best+1;
    }
}

如果你已经找到了这行代码的答案，请返回该答案。如果队列中没有人，则您已经完成，不需要再形成任何组。

假设无法组成任何组。然后尝试通过尝试行中所有类似思维的程序员的连续组来证明这一点错误。如果该组足够大以被选择，请看看删除此组后获取每个人进入餐厅需要多少次移动。跟踪所需的最小移动次数。

如果找不到消除所有组的方法，则返回-1。否则，返回消除组后所需的最少移动次数加上1以解释您在此步骤中所做的移动。

- Null Set

你能给出你的解决方案的复杂度和更多的解释吗？ - GEP

1

@dosdos 不清楚复杂度。 - Null Set

我相信你的解决方案在时间上可能会呈指数级增长。 - GEP

1

我认为这是指数级的。考虑一个长度为100且k=1的字符串HGHGHGHG...，这将会产生大量的递归调用。 - IVlad

我使用C#实现了这个，使用Dictionary作为哈希表，但是对于一个由我在之前评论中所说的方式构造的40个字符的字符串来说，它需要很长时间。肯定有一种方法可以解决它，因为很多人已经在SPOJ上解决了它。然而，我还没有看到它。 - IVlad

显示剩余3条评论

0

如何使用分治算法？取一个（可移动的）接近中间的组，以及它两边的两个组，比如...HHHGGGGGHHHHH... - 现在有两种可能性。要么这两组 H 在同一组中，要么不在。如果它们在同一组中，那么它们之间的 G 必须作为一个精确的 G 组被移除（所以你可以把它作为第一步尝试）。如果它们不在同一组中，则可以分别解决左右子列表。无论哪种情况，您都有一个更短的列表进行递归处理。

- Chris Nash

这个算法的时间复杂度是多少？ - GEP

我认为更简单的表述方式可能是你正在尝试标记每个删除操作的第一个和最后一个元素。我确信它有可能呈指数级增长，但我认为没有任何绕过这个问题的方法（你可以构造一些最坏情况序列），但希望你的竞赛输入会友好一些 :) - Chris Nash

其实我在考虑一个类似于矩阵链乘法的算法，它是这样的。 - GEP

将初始序列压缩为3 2 3，例如HHHGGHHH，然后找到每种可能组合的最佳方式，就像矩阵链乘法一样。我尝试过一些情况，它可以工作，但我不确定它是否普适。 - GEP

这是一个很好的问题。我非常想看看那个“聪明”的解决方案是什么。 - Chris Nash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user635541 · Accepted Answer

我希望您不要指望我为您实际解决SPOJ问题，因此请将以下内容视为多项式时间DP的存在证明。

对于固定的K，可以用上下文无关文法来表示能够就餐的字符串集合。我将使用“g”和“h”代替“G”和“H”。例如，对于K = 3，一个文法如下：

S -> ε | g S g S g S G | h S h S h S H

G -> ε | g S G

H -> ε | h S H

这个想法是，在任意两个用餐者之间（以及最后一个和末尾），存在一个可以用餐的字符串，要么就没有用餐者，要么第一个用餐者与至少K-1个其他人一起用餐。

现在使用CYK的加权变体来查找最小权重解析，其中非空S产生的权重为1，所有其他产生的权重均为0。对于固定的K，CYK的运行时间为O(N^3)。