Как Вы пошли бы о занятии этим осуществлением?

Введение:

Править: Посмотрите решение у основания этого вопроса (C++)

У меня есть конкурс программирования, подходящий в немного, и я готовился :)

Я практикую использование этих вопросов:

http://cemc.math.uwaterloo.ca/contests/computing/2009/stage2/day1.pdf

Я смотрю на проблему B ("Ужин").

Какая-либо идея, где запустить? Я ни о чем не могу действительно думать помимо наивного подхода (т.е. пробующий все перестановки), который занял бы слишком много времени быть действительным ответом.

Btw, язык там говорит, что C++ и Паскаль, я думаю, но я не забочусь о том, какой язык Вы используете - я имею в виду действительно все, что я хочу, подсказка относительно направления, я должен продолжить двигаться в, и возможно короткое объяснение для соглашений с ним. Такое чувство, что я пропускаю что-то очевидное...

Конечно, расширенное предположение является больше, чем приветствие, но я просто хотел разъяснить, что я не ищу полное решение здесь :)

---

Короткая версия вопроса:

У Вас есть двоичная строка N длины 1-100 (в вопросе, они используют H и G вместо и 0). Необходимо удалить все цифры от него в наименьшем количестве количества возможных шагов. На каждом шаге можно удалить любое количество смежных цифр, пока они - то же. Таким образом, на каждом шаге можно удалить любое число смежного G или любое число смежного H, но Вы не можете удалить H и G за один шаг.

Пример:

HHHGHHGHH

Решение примера:

1. HHGGHH (remove middle Hs)
2. HHHH (remove middle Gs)
3. Done (remove Hs)
   -->Would return '3' as the answer.

Обратите внимание, что может также быть граница, установленная для того, как многочисленные смежные группы должны быть, когда Вы удаляете их. Например, это могло бы сказать '2', и затем Вы не можете удалить единственные цифры (необходимо было бы удалить пар или более многочисленные группы за один раз).

Решение

Я взял основной алгоритм Mark Harrison и идею группировки Парадигмы и использовал их для создания решения ниже. Можно испытать его на официальных тестовых сценариях, если Вы хотите.

//B.cpp
//include debug messages?
#define DEBUG false


#include 
#include 
#include 

using namespace std;

#define FOR(i,n) for (int i=0;itype=type;
        num=1;
    }
};

//n is the number of bits originally in the line
//k is the minimum number of people you can remove at a time
//moves is the counter used to determine how many moves we've made so far
int n, k, moves;
int main(){

    /*Input from File*/
    scanf("%d %d",&n,&k);
    char * buffer = new char[200];
    scanf("%s",buffer);

    /*Process input into a vector*/
    //the 'line' is a vector of 'String's (essentially contigious groups of identical 'bits')
    vector line;
    line.push_back(String());
    FOR(i,n){

        //if the last String is of the correct type, simply increment its count
        if (line.back().type==buffer[i])
            line.back().num++;

        //if the last String is of the wrong type but has a 0 count, correct its type and set its count to 1
        else if (line.back().num==0){
            line.back().type=buffer[i];
            line.back().num=1;
        }

        //otherwise this is the beginning of a new group, so create the new group at the back with the correct type, and a count of 1
        else{
            line.push_back(String(buffer[i]));
        }

    }

    /*Geedily remove groups until there are at most two groups left*/
    moves=0;
    int I;//the position of the best group to remove
    int bestNum;//the size of the newly connected group the removal of group I will create
    while (line.size()>2){

        /*START DEBUG*/
        if (DEBUG){
            cout<<"\n"<bestNum && line[i].num>=k){
                bestNum=line[i-1].num+line[i+1].num;
                I=i;
            }
        }
        //remove the chosen group, thus merging the two adjacent groups
        line[I-1].num+=line[I+1].num;
        line.erase(line.begin()+I);
            line.erase(line.begin()+I);

            //we just performed a move
        moves++;
    }

    /*START DEBUG*/
    if (DEBUG){
        cout<<"\n"<=k && line[1].num>=k)
        cout<=k)
        cout<

Некоторые официальные тестовые сценарии можно попробовать:

• Тест 3

  8 2
  GHHGHGGH
  

  Ответ: 4

• Тест 6

  20 2
  GGHGGHHGGGHHGHHGHHGG
  

  Ответ: 6

• Тест 14

  100 4
  HGHGGGHGGGHGHGGGHHGHGGGHHGHHHGHGGHGGHHHGGHHGHHGHGHHHHGHHGGGHGGGHGHGHHGGGHGHGHGGGHHGHHHGHGGGHGGGHGHHH
  

  Ответ:-1

  Объяснение:-1 производится, когда нет никакого корректного ответа.

• Тест 18

  100 5
  GHGGGGGHGGGGGGGHHHHGGGGGHGGHHHGGGGGHHHHGGHHHHHGGGGGGHHHHHHGGGHHHHHGHHGGHHHHHGGGHHGGHHGGGGGGHHHGGGGHH
  

  Ответ: 16

• Тест 21

  95 2
  GGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHG
  

  Ответ: 32