Java教程

2022杭电多校05 1006BBQ

本文主要是介绍2022杭电多校05 1006BBQ,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
}
这篇关于2022杭电多校05 1006BBQ的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!