Вступление:
РЕДАКТИРОВАТЬ: См. Решение в нижней части этого вопроса (c ++)
У меня скоро будет конкурс по программированию, и я 'я готовил:)
Я практикуюсь, используя следующие вопросы:
http://cemc.math.uwaterloo.ca/contests/computing/2009/stage2/day1.pdf
Я смотрю на проблему B ("Ужин").
Есть идеи, с чего начать?Я не могу придумать ничего, кроме наивного подхода (т. Е. Пробовать все перестановки), который может занять слишком много времени, чтобы быть правильным ответом.
Кстати, язык там говорит 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», и тогда вы не сможете удалить однозначные цифры (вам придется удалять пары или более крупные группы одновременно).
Решение
Я взял основной алгоритм Марка Харрисона и идею группировки Paradigm и использовал их для создания решения ниже.Вы можете попробовать его в официальных тестовых кейсах , если хотите.
//B.cpp
//include debug messages?
#define DEBUG false
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define FOR(i,n) for (int i=0;i<n;i++)
#define FROM(i,s,n) for (int i=s;i<n;i++)
#define H 'H'
#define G 'G'
class String{
public:
int num;
char type;
String(){
type=H;
num=0;
}
String(char type){
this->type=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<String> 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"<<moves<<"\n----\n";
FOR(i,line.size())
printf("%d %c \n",line[i].num,line[i].type);
cout<<"----\n";
}
/*END DEBUG*/
I=1;
bestNum=-1;
FROM(i,1,line.size()-1){
if (line[i-1].num+line[i+1].num>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"<<moves<<"\n----\n";
FOR(i,line.size())
printf("%d %c \n",line[i].num,line[i].type);
cout<<"----\n";
cout<<"\n\nFinal Answer: ";
}
/*END DEBUG*/
/*Attempt the removal of the last two groups, and output the final result*/
if (line.size()==2 && line[0].num>=k && line[1].num>=k)
cout<<moves+2;//success
else if (line.size()==1 && line[0].num>=k)
cout<<moves+1;//success
else
cout<<-1;//not everyone could dine.
/*START DEBUG*/
if (DEBUG){
cout<<" moves.";
}
/*END DEBUG*/
}
Некоторые из официальных тестовых кейсов вы можете попробовать:
Контрольный пример 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