一个动态规划问题

Question

谁能帮我找到这个问题的最佳动态规划算法

在去吃晚饭的路上， CCC 的参赛者正在排队享用美味的炸薯条。 N（1≤N≤100）名选手排成一队进入食堂。

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

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。

Answer 1

我不想以实际的方式为您解决 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³)。

Answer 2

子问题是让每个人在给定的排队状态下就餐所需的最小群体。有很多可能的行状态，但实际上只有少数几种，因此您的记忆可能应该使用哈希图来完成。

这是一些伪代码。

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。否则，返回删除一组后所需的最少移动量加一以说明您在此步骤中所做的移动。

Answer 3

分而治之怎么样？在中间附近的某个位置取一个（可移动的）组，在其两侧各取两个组，比如说……HHHGGGGGGHHHHH…… - 现在有两种可能性。这两组 H 要么在同一组用餐，要么不同。如果他们在同一组中用餐，那么他们之间的那些 G 必须作为一组恰好这些 G 被移除（所以你不妨尝试将其作为你的第一步）。如果没有，那么您可以分别求解左右子列表。无论哪种情况，您都会得到一个更短的递归列表。