Cheapest Palindrome,POJ,3280

题目描述：Cheapest Palindrome (POJ 3280)

给定一个字符串和一个字符的插入和删除成本表，要求将字符串转换为回文串的最小成本。

输入：

• 第一行包含两个整数 N 和 M，分别表示字符串的长度和字符集的大小。
• 第二行包含一个长度为 N 的字符串 S。
• 接下来的 M 行，每行包含一个字符 c 和两个整数 a 和 b，分别表示字符 c 的插入成本和删除成本。

输出：

• 输出一个整数，表示将字符串 S 转换为回文串的最小成本。

示例：

输入： 5 3 abcba a 1 2 b 3 4 c 5 6

输出： 0

解题思路：

1. 动态规划：
   • 使用一个二维数组 dp[i][j] 表示将字符串 S[i...j] 转换为回文串的最小成本。
   • 初始化：dp[i][i] = 0，因为单个字符本身是回文。
   • 状态转移：
     • 如果 S[i] == S[j]，则 dp[i][j] = dp[i+1][j-1]。
     • 如果 S[i] != S[j]，则 dp[i][j] = min(dp[i+1][j] + del[S[i]], dp[i][j-1] + ins[S[j]])，其中 ins 和 del 分别表示插入和删除成本。
2. 边界处理：
   • 处理好字符串的两端，逐步向中间靠拢。
3. 优化：
   • 可以使用滚动数组优化空间复杂度。

代码实现（C++）：

#include #include #include #include

map> cost;
for (int i = 0; i < M; ++i) {
    char c;
    int ins, del;
    cin >> c >> ins >> del;
    cost[c] = {ins, del};
}

vector> dp(N, vector(N, 0));

for (int len = 2; len <= N; ++len) {
    for (int i = 0; i <= N - len; ++i) {
        int j = i + len - 1;
        if (S[i] == S[j]) {
            dp[i][j] = dp[i + 1][j - 1];
        } else {
            dp[i][j] = min(dp[i + 1][j] + cost[S[i]].second, dp[i][j - 1] + cost[S[j]].first);
        }
    }
}

cout << dp[0][N - 1] << endl;
return 0;

}

解释：

1. 输入处理：
   • 读取字符串长度 N 和字符集大小 M。
   • 读取字符串 S。
   • 读取每个字符的插入和删除成本，存储在 cost 映射中。
2. 动态规划初始化：
   • 创建一个 N x N 的二维数组 dp，初始化为0。
3. 状态转移：
   • 外层循环遍历所有可能的子串长度 len。
   • 内层循环遍历所有可能的子串起始位置 i。
   • 根据 S[i] 和 S[j] 是否相等，更新 dp[i][j]。
4. 输出结果：
   • 最终结果存储在 dp[0][N-1] 中，表示将整个字符串转换为回文串的最小成本。

复杂度分析：

• 时间复杂度：O(N^2)，因为需要遍历所有子串。
• 空间复杂度：O(N^2)，因为使用了一个二维数组存储状态。

通过上述方法，可以有效地求解将给定字符串转换为回文串的最小成本问题。