Hdu2022 Multi-School Training (5) BBQ

题意：
给定一个字符串,Can be arbitrarily increased censored,Make it as a set of four characters are for palindrome string,问最小操作步数

#include<bits/stdc++.h>
using namespace std;
int t[10];
int g[10][5];// 原长度为g[i][j] As the original length ofiPattern string into a length ofjThe mode of list of the shortest edit distance
int w[3000000];//The pattern string map into a digital,On behalf of its weight
void dfs(int n, int c, int idx)//Pretreatment of each pattern string into a legitimate substring needed to consume.
{
       
   // 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]For the current length ofiSteps into legal conditions of minimum
int last[26];
int pre[1000001];//Each character to appear on a position
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)//In the presence of a position is in the fronti个,That is a new letter
                idx = idx * 10 + (tmp[j] = ++cnt);
            else//Before the current character is equal to the encoding of the characters
                idx = idx * 10 + (tmp[j] = tmp[pre[i + j] - i]);//The current string into a string into the corresponding mode values.
            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();
}