Moe's CF Life

Appearance

F. Clear the String - 题解 ​

比赛与标签 ​

比赛: Educational Codeforces Round 61 (Rated for Div. 2) 标签: dp, *2000 难度: *2000

题目大意，听我讲喵！ ​

主人，这道题是这样子的呐：

我们拿到一个由小写字母组成的字符串 s。我们可以对它施展一个魔法：选择一段连续且所有字符都相同的子串，然后 "咻" 的一下把它整个删除掉！比如说，字符串 abbbaccdd 里的 bbb 就是这样一段，删除它之后，字符串就变成 aaccdd 啦。

我们的任务就是，用最少的魔法次数，把整个字符串 s 完全消除掉。请告诉本喵，最少需要多少次魔法呢？

输入:

  • 第一行是一个整数 n，代表字符串的长度。
  • 第二行是长度为 n 的字符串 s。

输出:

  • 一个整数，表示最少的操作次数。

比如 abaca，最少需要 3 次操作的说。可以先删 b -> aaca，再删 c -> aa，最后删 aa -> 空。一共三次，喵~

解题思路，跟我来喵~ ​

这道题看起来是在一个区间上进行操作，求最优解，这种感觉... 没错了！就是区间动态规划 (Interval DP) 的味道，喵~

区间DP通常用来解决与子串、子序列相关的问题。它的核心思想就是，通过解决小区间的问题，来一步步地推导出大区间问题的答案。

第一步：压缩字符串！ ​

在开始DP之前，我们先来做一个小小的预处理，让问题变得更简单一些。注意到，像 aaabbc 这样的字符串，中间的 aaa 无论多长，我们都可以用一次操作就把它删掉。所以，从操作次数的角度看，aaabbc 和 abc 其实是等价的！

所以，我们可以先把原字符串 s 压缩一下，把连续相同的字符合并成一个。比如 aaabbc -> abc，abbbba -> aba。这样处理之后，字符串里就不会有相邻的相同字符了，分析起来会清晰很多，喵！

第二步：设计DP状态！ ​

既然是区间DP，那我们的状态肯定和区间有关啦。我们定义 dp[i][j] 表示：消除压缩后字符串的子串 s[i..j] 所需要的最少操作次数。

我们的最终目标，自然就是求出 dp[0][n-1]，其中 n 是压缩后字符串的长度。

第三步：思考状态转移方程~ ​

这是最激动人心的部分了！我们来想一想，对于一个区间 s[i..j]，我们该如何消除它呢？我们可以把目光聚焦在区间的第一个字符 s[i] 上。处理它有两种策略：

策略一：单独删除 s[i] 最简单粗暴的方法，就是直接用一次操作把 s[i] 这个字符（因为它自己就是一个长度为1的连续相同块）删掉。这次操作花费了 1 次。之后，我们剩下的任务就是消除子串 s[i+1..j]，这个子问题的答案我们已经（或者将会）算出来，就是 dp[i+1][j]。 所以，这种策略的总花费是 1 + dp[i+1][j]。

策略二：和后面的相同字符一起删除！ 这是一个更聪明的策略，喵~ 我们可以不立即删除 s[i]，而是找找看在 s[i] 后面，也就是 s[i+1..j] 这个区间里，有没有和 s[i] 相同的字符。

假设我们在位置 k (i < k <= j) 找到了一个字符 s[k]，并且 s[k] == s[i]。 这给了我们一个机会！我们可以把删除 s[i] 的操作和删除 s[k] 的操作“合并”起来。要做到这一点，我们必须先把它们之间的“障碍物”——也就是子串 s[i+1..k-1]——全部清除掉。清除这部分的花费是 dp[i+1..k-1]。

当中间的 s[i+1..k-1] 被清空后，s[i] 和 s[k] 就“挨”在一起了。此时，我们再去处理 s[k..j] 这部分。因为 s[i] 和 s[k] 相同，那个原本要删除 s[k] 的操作就可以顺便把 s[i] 也带走，不需要额外的花费！所以，处理剩下部分 s[k..j]（包括s[i]）的总花费就是 dp[k][j]。

因此，这个策略的总花费是 dp[i+1][k-1] + dp[k][j]。

注意一个小细节：当 k = i + 1 时，中间的子串 s[i+1..k-1] 就是 s[i+1..i]，这是一个空区间。消除空区间当然不需要任何操作，花费为 0。我们的DP表初始化为0，正好可以完美处理这种情况！

最终的转移方程: 对于 dp[i][j]，我们要在所有可能的策略中选择一个花费最小的。也就是： dp[i][j] = min( 1 + dp[i+1][j], min_{k=i+1 to j, if s[k]==s[i]} (dp[i+1][k-1] + dp[k][j]) )

第四步：确定计算顺序 ​

DP的计算需要从小区间到大区间。我们先计算所有长度为 1 的区间的 dp 值，然后是长度为 2，长度为 3，... 一直到长度为 n。

  • Base Case: 当区间长度为 1 时，即 dp[i][i]，只需要 1 次操作就能删除。所以 dp[i][i] = 1。
  • 迭代: 我们用一个循环 len 从 2 到 n 来表示区间的长度，再用一个循环 i 来枚举区间的起点，终点 j 就是 i + len - 1。这样就能保证我们计算 dp[i][j] 时，所有比它小的子区间的 dp 值都已经被算好啦！

这样一步步下来，我们就能得到最终的答案 dp[0][n-1] 啦！是不是很清晰呢，喵~

代码实现喵！ ​

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// dp[i][j] 将存储消除子串 s[i..j] 的最小操作次数，喵~
// 使用全局数组在竞赛中很方便，它会被自动初始化为0，这对空区间的处理很有帮助。
int dp[501][501];

int main() {
    // 快速I/O，让程序跑得更快一点！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n_orig;
    std::cin >> n_orig;
    std::string s_orig;
    std::cin >> s_orig;

    // 预处理步骤：压缩字符串，把连续相同的字符合并成一个。
    // "aaabbc" 的最小操作数和 "abc" 是一样的说。
    // 因为任何连续的相同字符块都可以在一次操作中被删除。
    // 所以原问题等价于在压缩后的字符串上的问题。
    std::string s;
    if (n_orig > 0) {
        s.push_back(s_orig[0]);
        for (int i = 1; i < n_orig; ++i) {
            if (s_orig[i] != s.back()) {
                s.push_back(s_orig[i]);
            }
        }
    }
        
    int n = s.length();

    // 题目保证 n >= 1，所以压缩后 n 也 > 0。这个检查是为了健壮性。
    if (n == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // Base Case：长度为1的子串需要1次操作。
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }

    // 按区间长度从小到大进行迭代，从长度2到n。
    for (int len = 2; len <= n; ++len) {
        // 枚举所有长度为 len 的子串的起始位置 i。
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;

            // 我们来计算 dp[i][j]，考虑对第一个字符 s[i] 的操作。
            // 策略一：单独删除 s[i]。
            // 花费是 1 (删除s[i]) + 消除剩余部分s[i+1..j]的花费。
            // 这是我们对 dp[i][j] 的一个初始估计值。
            dp[i][j] = 1 + dp[i + 1][j];

            // 策略二：将 s[i] 与后面的某个相同字符 s[k] 合并删除。
            // 要做到这点，必须先清空它们之间的子串 s[i+1..k-1]。
            // 之后，s[i] 和 s[k] 就“相邻”了。消除 s[i]s[k..j] 的花费
            // 就等于消除 s[k..j] 的花费，因为删除 s[k] 的操作可以免费“顺带”上 s[i]。
            for (int k = i + 1; k <= j; ++k) {
                if (s[i] == s[k]) {
                    // 花费 = (清空 s[i+1..k-1]) + (清空 s[k..j])
                    // 如果 k = i+1, 中间部分 s[i+1..i] 是空的，花费为0。
                    // 我们的dp表是0初始化的，所以dp[i+1][k-1] (即dp[i+1][i]) 正好是0，完美！
                    int merge_cost = dp[i + 1][k - 1] + dp[k][j];
                    dp[i][j] = std::min(dp[i][j], merge_cost);
                }
            }
        }
    }

    // 答案就是消除整个压缩后字符串的最小操作次数。
    std::cout << dp[0][n - 1] << std::endl;

    return 0;
}

复杂度分析的说~ ​

  • 时间复杂度: O(n³) 的说。我们有三层嵌套循环：最外层是区间长度 len (从 1 到 n)，第二层是起始位置 i (从 0 到 n)，最内层是寻找合并点 k (从 i 到 j)。所以总的时间复杂度是 O(n³)。对于 n=500，这个复杂度是可以接受的。
  • 空间复杂度: O(n²) 的说。我们主要用了一个 dp 二维数组，大小为 n x n，所以空间复杂度是 O(n²)。

知识点与总结 ​

这道题真是一道非常经典的区间DP题，做完之后感觉又变强了呢，喵~

  1. 核心算法思想: 区间动态规划 (Interval DP) 是解决这类问题的利器。它的模板通常是枚举区间长度，再枚举区间起点，通过子问题的解来构建当前问题的解。
  2. 预处理的重要性: 解决问题前先观察和简化问题，往往能事半功倍！这里的字符串压缩就是一个非常棒的例子，它剔除了无关紧要的信息，让我们的DP状态定义和转移都变得更加纯粹和简单。
  3. DP状态转移的思考方式: 对于 dp[i][j]，抓住区间的一个端点（比如 s[i]）来分析，思考所有可能处理它的方式（单独处理 vs 和其他元素合并处理），然后取最优，这是一种非常有效的推导状态转移方程的方法。
  4. 边界条件处理: DP问题中，边界条件和空区间的处理非常关键。dp 数组初始化为0，以及循环的起止点，都需要小心翼翼地设置才能得到正确答案哦！

希望这篇题解能帮助到大家！以后也要和我一起快乐地刷题呀，喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe