hihoCoder #1039 字符消除

目前除了暴力穷举，还没有想出更好的办法。在我的代码里枚举分为两类：

在字符间添加同一\两侧之一相同的字符，如向“BC”中添加B或C；
在字符间添加与一\两侧均不相同的字符，如向“BC”中添加A。

之后，将新字符串按连续字符整理为块，再进行操作模拟。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <string>
#include <limits>
#include <algorithm>
using namespace std;

const int MAX_LEN = 101;

struct Item
{
    Item(char rc, int rcnt) : c(rc), cnt(rcnt) {}
    char c;
    int cnt;
};

vector<Item> build_form(char *str)
{
    size_t len = strlen(str);
    vector<Item> form;
    int i = 0, i1 = 1;
    while (i1 < len)
    {
        while (str[i1] == str[i]) i1++;
        form.push_back(Item(str[i], i1 - i));
        i = i1;
        i1++;
    }
    if (i<len) form.push_back(Item(str[i], i1 - i));
    return form;
}

void merge_form(vector<Item> &form)
{
    if (form.empty()) return;
    bool bCont = true;
    while (bCont)
    {
        int i = 0;
        while (i < form.size() - 1 && form[i].c != form[i + 1].c) i++;
        if (i == form.size() - 1)
        {
            bCont = false;
        }
        else
        {
            form[i].cnt += form[i + 1].cnt;
            form.erase(form.begin() + i + 1);
        }
    }
}

int calc(vector<Item> form)
{
    int ret = 0;

    bool bCont = true;
    while (bCont)
    {
        vector<int> taken;
        for (int i = 0; i < form.size(); i++)
        {
            if (form[i].cnt > 1)
            {
                ret += form[i].cnt;
                taken.push_back(i);
            }
        }
        if (!taken.empty())
        {
            int delcnt = 0;
            for (int k = 0; k < taken.size(); k++)
            {
                int j = taken[k];
                int offset = j - delcnt;
                if (offset < form.size() - 1)
                    form.erase(form.begin() + offset);
                else
                    form.pop_back();
                delcnt++;
            }
            merge_form(form);
        }
        else
        {
            bCont = false;
        }
    }

    return ret;
}

int try_add_item_at(char *str, int i, char c)
{
    string s(str);
    s.insert(s.begin() + i, c);
    vector<Item> form = build_form((char *)s.c_str());
    return calc(form);
}

int try_item_at(vector<Item> form, int i)
{
    form[i].cnt++;
    return calc(form);
}

int del(char *str)
{
    size_t len = strlen(str);
    if (len == 0) return 0;
    if (len == 1) return 2;
    
    vector<Item> form = build_form(str);

    //
    int ret = std::numeric_limits<int>::min();
    for (int i = 0; i < form.size(); i++)
    {
        ret = std::max(ret, try_item_at(form, i));
    }
    for (int i = 0; i < len; i++)
    {
        bool val[] = {true, true, true};
        if (i == 0)
        {
            val[str[0] - 'A'] = false;
        }
        else if (i == len - 1)
        {
            val[str[i] - 'A'] = false;
        }
        else
        {
            val[str[i] - 'A'] = false;
            val[str[i + 1] - 'A'] = false;
        }
        for (int j = 0; j < 3; j++)
        {
            if (val[j])
                ret = std::max(ret, try_add_item_at(str, i, 'A' + j));
        }
    }
    return ret;
}

int main()
{
    int t; scanf("%d", &t);
    while (t--)
    {
        char in[MAX_LEN] = {0};
        scanf("%s", in);

        int ret = del(in);
        printf("%d\n", ret);
    }
    return 0;
}

View Code

hihoCoder #1039 字符消除

推荐阅读