2019.9.11 VIVO笔试消消乐题解 DFS

//题目： 开心消消乐，输入1 4 2 2 3 3 2 4 1， 返回21（先消3 3，得分为2*2=4；再消2 2 2，得分为3*3=9；再消4 4，得分为4；再消1 1，得分为4； 所以总得分4+9+4+4+4=21）
//方法：DFS
int nDelete(vector<int> boxs) //有n个可以消的地方
{
    int N = boxs.size();
    int n = 0; //有n个可以消的地方
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; i + j < N; j++)
        {
            if (boxs[i] != boxs[i + j])
            {
                i += (j-1);
                break;
            }
                if(j == 1)
                    n++;
                continue;
    }
    return n;
}

int score(vector<int> boxs) //得分
{
    int N = boxs.size();
    int size = boxs.size();     //数组大小
    int n = nDelete(boxs); //还有几处可以删除
    if (n == 0) //假如数组没有可以消的了，返回0
    return 0;

    vector<int> res; //里面存的是n种消除的情况，取最终得分最大的输出
    for (int i = 0; i < N; i++)
    {
        int j = 1; //有j个重复的
        for ( ; i + j < N; j++)
        {
            if (boxs[i] != boxs[i + j])
            {
                i += (j - 1);
                break;
            }
        }

        int tempscore = 0; //返回消除当前连续块的得分
        vector<int> newboxs;
        if (j > 1) //有重复的才消除
        {
            for (int k = 0; k < i - j + 1; k++)
                newboxs.push_back(boxs[k]);
            for (int k = i + 1; k < N; k++)
               newboxs.push_back(boxs[k]);

            tempscore += j * j + score(newboxs);
            res.push_back(tempscore);
            if (res.size() == n)
                break;
        }
    }
    auto maxPosition = max_element(res.begin(), res.end());
    int result = *maxPosition;
    return result;
}

int main()
{
    string s;
    getline(cin, s);
    stringstream ss(s);
    vector<int> boxs;
    int temp;
    while (ss >> temp)
    {
        boxs.push_back(temp);
    }

    int num = score(boxs);
    cout << num << endl;
    return 0;
}
#vivo##题解##笔试题目##校招#