给定一个字符串\(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; }