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

Question

Может ли кто-нибудь помочь мне найти оптимальный алгоритм динамического программирования для этой проблемы

На пути к обеду участники ССС выстраиваются в очередь за своими вкусными кудрявыми картошками фри.Участники N (1 ≤ N ≤ 100) выстроили в очередь один файл для входа в кафетерий.

Доктор V, который руководит CCC, в последнюю минуту понял, что программисты просто ненавидят стоять в очереди рядом с программистамикто использует другой язык.К счастью, в 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 представляет файл справки, 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

Идея состоит в том, что либо нет обедающих, либо первый обедающий обедает по крайней мере с К - 1, между любыми двумя из которых (и последним, и концом) есть строка, которая может обедать.

Теперь используйте взвешенный вариант CYK , чтобы найти синтаксический анализ минимального веса, где непустые произведения S имеют вес 1, а все остальные имеют вес 0. Для фиксированного K время работы CYK равно O (N ³ ).

Answer 2

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

Answer 3

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

Вот некоторый псевдокод.

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