Задача динамического программирования.

Я бы предпочел не решать проблему 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³).

Подзадача — минимальные группы, необходимые для того, чтобы все обедали при заданном состоянии очереди. Существует множество возможных состояний строк, но только некоторые из них будут видны на самом деле, поэтому вам, вероятно, следует выполнять запоминание с помощью хэш-карты.

Вот какой-то псевдокод.

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. В противном случае верните наименьшее количество ходов, необходимых после удаления группы, плюс один, чтобы учесть ход, сделанный на этом шаге.

Как насчет разделяй и властвуй? Возьмите (съемную) группу где-то ближе к середине, а две группы по бокам от нее, скажите ...HHHGGGGGHHHHH.... - теперь есть две возможности. Либо эти 2 набора H обедают в одной группе, либо нет. Если они обедают в одной группе, то эти G между ними должны быть удалены как группа точно этих G (поэтому вы можете попробовать это в качестве первого хода). Если нет, то вы можете найти левый и правый подсписки отдельно. В любом случае у вас есть более короткий список для рекурсии.