字符消除
字符消除
https://www.nowcoder.com/practice/c2d5576d39bf41e99bbe2f5ac9270889
字符消除
[题目链接](https://www.nowcoder.com/practice/c2d5576d39bf41e99bbe2f5ac9270889)
思路
本题要求将一个偶数长度的字符串通过反复删除相邻字符对完全消除，使得总花费最大化。每次删除相邻的字符 和
花费
，删除后左右两部分拼接。
区间 DP
这是一个经典的区间 DP 问题。定义 为将子串
完全消除所能获得的最大花费（
必须为偶数才可能消除干净）。
转移思路：考虑 最终和谁配对消除。
必须和某个
配对，其中
与
的距离为奇数（即
），这样
和
之间的子串长度为偶数，可以先被完全消除，使得
和
变为相邻后再删除。
转移方程：
$$
其中空区间的 值为
。
样例演示
字符串 abac（）：
- 方案一：先删
ab（花 1），剩ac，再删ac（花 3），总花费 4。 - 方案二：
a和a（位置 0 和 2）配对。先删中间的b和a（即ba，花 2），然后a和c相邻，删除花 3。但这里配对
，需要先消除
（长度为奇数，不可能），所以不可行。
- 实际最优：
，先消除
（花 2），再删
和
（花 3），总计 5。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<vector<int>> cost(k, vector<int>(k));
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
scanf("%d", &cost[i][j]);
char s[510];
scanf("%s", s);
// dp[i][j] = max cost to eliminate s[i..j] completely, -1 if impossible
vector<vector<long long>> dp(n, vector<long long>(n, -1));
for (int i = 0; i + 1 < n; i++) {
dp[i][i + 1] = cost[s[i] - 'a'][s[i + 1] - 'a'];
}
for (int len = 4; len <= n; len += 2) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
for (int m = i + 1; m <= j; m += 2) {
long long left = 0, right = 0;
if (m > i + 1) {
if (dp[i + 1][m - 1] < 0) continue;
left = dp[i + 1][m - 1];
}
if (m < j) {
if (dp[m + 1][j] < 0) continue;
right = dp[m + 1][j];
}
long long val = left + cost[s[i] - 'a'][s[m] - 'a'] + right;
dp[i][j] = max(dp[i][j], val);
}
}
}
printf("%lld\n", dp[0][n - 1]);
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), 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 (long[] row : dp) Arrays.fill(row, -1);
for (int i = 0; i + 1 < n; i++) {
dp[i][i + 1] = cost[s.charAt(i) - 'a'][s.charAt(i + 1) - 'a'];
}
for (int len = 4; len <= n; len += 2) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
for (int m = i + 1; m <= j; m += 2) {
long left = 0, right = 0;
if (m > i + 1) {
if (dp[i + 1][m - 1] < 0) continue;
left = dp[i + 1][m - 1];
}
if (m < j) {
if (dp[m + 1][j] < 0) continue;
right = dp[m + 1][j];
}
long val = left + cost[s.charAt(i) - 'a'][s.charAt(m) - 'a'] + right;
dp[i][j] = Math.max(dp[i][j], val);
}
}
}
System.out.println(dp[0][n - 1]);
}
}
复杂度分析
- 时间复杂度：
。三层循环：枚举区间长度、起点、配对位置。
- 空间复杂度：
，存储 DP 表。
