你会如何解决这个问题呢？

Question

介绍:

编辑:请参阅此问题底部的解决方案(c ++)

我有一个编程竞赛,我一直在准备:)

我正在练习使用这些问题:

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

我在看问题B("晚餐").

知道从哪里开始？除了天真的方法(即尝试所有排列)之外我无法想到任何需要太长时间才能成为有效答案的方法.

顺便说一句,那里的语言是c ++和pascal我认为,但我不在乎你用的是什么语言 - 我的意思是我想要的只是暗示我应该继续进行的方向,并简要介绍一下简短的解释它.感觉我错过了一些明显的东西......

当然,扩展的猜测是非常受欢迎的,但我只想澄清一点,我不是在寻找一个完整的解决方案:)

---

问题的简短版本:

你有一个长度为1-100的二进制字符串N(在问题中他们使用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的主要算法和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

Answer 1

执行以下步骤：

• 寻找诸如 H+G+H+ 之类的模式。删除一个 G+，留下合并的 H+，其中一个或多个原始 H+H+ 由于长度限制而无法删除。否则删除最长的合并 H+。
• G+H+G+ 也是如此。

重复上述步骤。每一步都会合并更大的 H+ 或 G+ 组。

最终您将拥有一个 H+ 和一个 G+（假设您一开始就有 H 和 G）。删除那些。

（H+、G+表示x个或多个H或G，其中x是一次可以去除的最小数。）