题解 | #字符消除#

题目链接

字符消除

题目描述

给定一个长度为 $n$ （ $n$ 为偶数）的、由前 $k$ 个小写字母组成的字符串。

我们可以执行一种操作：选择字符串中两个相邻的字符并删除它们，删除后剩余部分拼接起来。删除字符 $c_1$ 和 $c_2$ （ $c_1$ 在左， $c_2$ 在右）需要花费 $cost[c_1][c_2]$ 。

目标是求出将整个字符串完全消除所能得到的最大总花费。

解题思路

这是一个典型的区间动态规划问题。由于每次消除操作都会使原本不相邻的字符变得相邻，这提示我们子问题的解会相互影响，符合区间DP的特征。

1. DP状态定义

我们定义一个二维DP数组 dp[i][j]，表示将原始字符串中下标从 $i$ 到 $j$ 的子串（s[i...j]）完全消除所能获得的最大花费。

我们的最终目标是求解 dp[0][n-1]。

2. DP状态转移

我们按照区间长度 len 从小到大的顺序来计算DP值。对于一个区间 [i, j]，其长度为 len = j - i + 1。

基本情况：
- 如果 len 是奇数，该子串不可能被完全消除，所以 dp[i][j] = 0（或一个极小值表示无效）。
- 如果 len = 2，即 j = i + 1，那么 dp[i][i+1] 就是直接消除 s[i] 和 s[i+1] 的花费 cost[s[i]][s[i+1]]。
一般情况（len > 2 且为偶数）：我们考虑如何消除子串 s[i...j]。一种方式是将这个大问题分解为两个独立的、不重叠的子问题。我们可以选择一个分割点 p（从 i+1 到 j-1），先将子串 s[i...p] 完全消除，再将子串 s[p+1...j] 完全消除。
- 此时，总花费是 dp[i][p] + dp[p+1][j]。我们需要遍历所有可能的分割点 p 来找到最大值。
然而，这种分割方式忽略了一种重要情况：s[i] 与 s[j] 配对消除。要让 s[i] 和 s[j] 相邻，它们之间的子串 s[i+1...j-1] 必须先被完全消除。
- 这种策略的花费是 dp[i+1][j-1] + cost[s[i]][s[j]]。
综合以上两种策略，我们可以得到完整的状态转移方程： $dp[i][j] = \max($ $\qquad \max_{p=i+1, i+3, \dots, j-1} \{ dp[i][p] + dp[p+1][j] \},$ $\qquad dp[i+1][j-1] + cost[s[i]][s[j]]$ $)$

注意：分割点 $p$ 必须使得子区间 [i, p] 和 [p+1, j] 的长度都为偶数，因此 $p$ 的步长是2。

3. 遍历顺序

我们按照区间长度 len 从 2 到 $n$ （步长为2）进行遍历。对于每个 len，我们再遍历所有可能的左端点 $i$ ，右端点 $j$ 自然就是 $i + len - 1$ 。这样可以确保在计算 dp[i][j] 时，所有它依赖的更小子区间的DP值都已经被计算出来了。

代码

cpp
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> cost(k, vector<int>(k));
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> cost[i][j];
        }
    }

    string s;
    cin >> s;

    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int len = 2; len <= n; len += 2) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;

            // 策略1: s[i] 与 s[j] 配对
            dp[i][j] = dp[i + 1][j - 1] + cost[s[i] - 'a'][s[j] - 'a'];

            // 策略2: 分割区间
            for (int p = i + 1; p < j; p += 2) {
                dp[i][j] = max(dp[i][j], dp[i][p] + dp[p + 1][j]);
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[][] cost = new int[k][k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                cost[i][j] = sc.nextInt();
            }
        }

        String s = sc.next();

        long[][] dp = new long[n][n];

        for (int len = 2; len <= n; len += 2) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                // 策略1: s[i] 与 s[j] 配对
                dp[i][j] = (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0) + cost[s.charAt(i) - 'a'][s.charAt(j) - 'a'];

                // 策略2: 分割区间
                for (int p = i + 1; p < j; p += 2) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][p] + dp[p + 1][j]);
                }
            }
        }

        System.out.println(dp[0][n - 1]);
    }
}

import sys

def main():
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n, k = map(int, line.split())
        
        cost = []
        for _ in range(k):
            cost.append(list(map(int, sys.stdin.readline().split())))
            
        s = sys.stdin.readline().strip()
        
        dp = [[0] * n for _ in range(n)]
        
        for length in range(2, n + 1, 2):
            for i in range(n - length + 1):
                j = i + length - 1
                
                # 策略1: s[i] 与 s[j] 配对
                val1 = (dp[i + 1][j - 1] if i + 1 <= j - 1 else 0) + cost[ord(s[i]) - ord('a')][ord(s[j]) - ord('a')]
                dp[i][j] = val1
                
                # 策略2: 分割区间
                for p in range(i + 1, j, 2):
                    dp[i][j] = max(dp[i][j], dp[i][p] + dp[p + 1][j])
                    
        print(dp[0][n - 1])

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：区间动态规划
时间复杂度：我们有三层循环来填充DP表：一层是区间长度 len（从 2 到 $n$ ），一层是左端点 i（从 0 到 $n-1$ ），最内层是分割点 p（从 i 到 j）。因此，总时间复杂度为 $O(n^3)$ 。
空间复杂度：需要一个二维数组 dp 来存储状态，其大小为 $n \cdot n$ 。所以空间复杂度是 $O(n^2)$ 。