Hdu2022 多校训练（5） BBQ

题意：
给定一个字符串，可以任意增删改，使其每四个字符为一组都为回文串，问最小操作步数

#include
using namespace std;
int t[10];
int g[10][5];// 原长度为g[i][j] 为原长度为i的模式串变为长度为j的模式串的最短编辑距离
int w[3000000];//将模式串映射成一个数字，代表其权值
void dfs(int n, int c, int idx)//预处理每个模式串变为合法子串所需要的消耗。
{   
   // cout << idx << endl;
    int m = 9999999;
    if (n)
        for (int a = 1; a <= 7; a++)
            for (int b = 1; b <= 7; b++)
            {
                int p[5] = { 0,a,b,b,a };
                memset(g, 1, sizeof g);
                for (int i = 0; i <= 4; i++)
                    g[0][i] = i;
                for (int i = 0; i <= 7; i++)
                    g[i][0] = i;
                for (int i = 1; i <= n; i++)
                    for (int j = 1; j <= 4; j++)
                        g[i][j] = std::min(std::min(g[i - 1][j] + 1, g[i - 1][j - 1] + (t[i] != p[j])), g[i][j - 1] + 1);
                if (g[n][4] < m)m = g[n][4];
            }
    if (n)w[idx] = m;
    if (n == 7)return;
    n++;
    for (int i = 1; i <= c; i++)
    {
        t[n] = i;
        dfs(n, c, idx * 10+ i);
    }
    t[n] = c + 1;
    dfs(n, c + 1, idx * 10 + c + 1);
}

char s[1000001];
int dp[1000001];// dp[i]为当前长度为i变成合法条件的最小步数
int last[26];
int pre[1000001];//每个字符出现的上一个位置
void sol()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    memset(dp + 1, 10, n * 4);
    memset(last, -1, sizeof last);
    for (int i = 1; i <= n; i++)//映射方法
    {
        pre[i] = last[s[i] - 'a'];
        last[s[i] - 'a'] = i;
    }
    for (int i = 0; i < n; i++)
    {
        dp[i + 1] = std::min(dp[i + 1], dp[i] + 1);
        int cnt = 0;int idx = 0; int tmp[8];
        for (int j = 1; j <= 7; j++)tmp[j] = 0;
        for (int j = 1; j <= 7 && i + j <= n; j++)
        {
            //int c = s[i + j] - 'a';
            if (pre[i + j] <= i)//在上一个出现的位置是在前i个,说明是一个新的字母
                idx = idx * 10 + (tmp[j] = ++cnt);
            else//当前字符等于之前的字符的编码
                idx = idx * 10 + (tmp[j] = tmp[pre[i + j] - i]);//将当前串变为模式串并转换成相应下标值。
            dp[i + j] = std::min(dp[i + j], dp[i] + w[idx]);
        }
    }
    printf("%d\n", dp[n]);
}
int main()
{
    dfs(0, 0, 0);
    int t;
    scanf("%d", &t);
    while (t--)sol();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76