2022杭电多校05 1006BBQ

大致题意

给定一个字符串\(s\)，要求计算最小的数\(k\)，使得从\(s\)中删除\(k\)个字符后，每四个字母都满足\(abba\)的形式(不一定需要是字符\(a,b\)，满足形式即可)。

赛中拿到这道题的时候，第一个想到的是20ECFinal的namomo Sequence，试图枚举每四个字符的形态然后dp，然而纠结了半天只能拿出一个\(O(26 * 26 * n)\)时空复杂度的算法，想了很久没法优化于是作罢。看完题解以及标称之后才发现自己还是太naive。这篇博客主要就是通过代码介绍一下题解的精妙解法。

基本原理

通过分析性质我们可以发现，对于原串，我们可以对每一段不超过7的区间进行处理，使其变成一段abba形式的串。为什么枚举的区间长度不超过7？因为如果区间长度\(8\leq n\),如果变成一个组，需要代价不少于\(n-4\),而划分成两个组，每个组花费\(2\)进行修改，消耗不会高于\(n-4\)，比分为1组的更优。

得知该性质后，我们就可以枚举所有长度不超过7的段，枚举所有状态转移到\(abba\)形式的代价（不难发现状态数其实并不多）。预处理完后，我们就可以在原串上做一个常数为7的线性dp，不断向后转移，就能够得到最终答案。

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

const int maxn = 2e6;

int t[10];  //记录当前串
int g[10][5];   //g[i][j],当前串匹配到i,目标串匹配到j的消耗
int w[3000000]; //方案数

void dfs(int n, int c, int idx) { // n:长度 c:字符数 idx:状态
    int m = INF;    //当前状态的最优转化方案，初值设为无穷大。
    if (n) {
        for (int a = 1; a <= 7; a++) {  //这一段的dp转移目的在于计算将当前串转为目标串的最小花费
            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++) //初始化，最坏情况是全部删除，故结果为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] = min({ g[i - 1][j] + 1,g[i][j - 1] + 1,g[i - 1][j - 1] + (t[i] != p[j]) });//dp转移
                    }
                }
                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++) {//使用7进制存储答案，每一位对应字符串上的每一位。转移时可以快速计算状态。
        t[n] = i;
        dfs(n, c, idx * 8 + i);  //枚举所有的字符（出现过）
    }
    t[n] = c + 1;
    dfs(n, c + 1, idx * 8 + c + 1);//出现了没出现的字符。
}

int dp[maxn + 10];
int last[30];
int pre[maxn + 10];

void solve() {
    string s;
    cin >> s;
    int n = s.length();
    s = " " + s;
    memset(dp, 0x3f, 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;
    }
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        dp[i + 1] = min(dp[i + 1], dp[i] + 1);//删除一个字符的朴素转移。
        int cnt = 0;
        int idx = 0;//当前串的状态值
        int tmp[8];//记录当前串，用于计算
        for (int j = 1; j <= 7 && i + j <= n; j++) {
            int c = s[i + j] - 'a';
            if (pre[i + j] <= i) //没有出现过，是新字母
                idx = idx * 8 + (tmp[j] = ++cnt);
            else    //当前的字母是出现过的
                idx = idx * 8 + (tmp[j] = tmp[pre[i + j] - i]);
            dp[i + j] = min(dp[i + j], dp[i] + w[idx]);
        }
    }
    cout << dp[n] << "\n";
}

int main() {
    freopen("1006.in", "a+", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    dfs(0, 0, 0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}