poj1741，poj3280 Cheapest Palindrome（回文串區間dp）

2023-11-19 阅读 24 评论 0

摘要：https://vjudge.net/problem/POJ-3280 猛刷簡單dp第一天第三題。 poj1741。這個據說是【求字符串通過增減操作變成回文串的最小改動次數】的變體。首先增減操作的實質是一樣的，所以輸入時求min。 dp[i][j]表示第i個字符到第j個字符中修改成回文串的最小代價。由于回文

https://vjudge.net/problem/POJ-3280

猛刷簡單dp第一天第三題。

poj1741。這個據說是【求字符串通過增減操作變成回文串的最小改動次數】的變體。

首先增減操作的實質是一樣的，所以輸入時求min。

dp[i][j]表示第i個字符到第j個字符中修改成回文串的最小代價。由于回文串的特殊性，這里兩層循環的遍歷方式跟常見的略有不同

這算是回文串dp的一種典型題目典型方法吧。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<map>
 8 #define lson l, m, rt<<1
 9 #define rson m+1, r, rt<<1|1
10 #define INF 0x3f3f3f3f
11 typedef unsigned long long ll;
12 using namespace std;
13 int n, m, a, b, dp[2010][2010];
14 map<char, int> mp;
15 char s[2010], c;
16 int main()
17 {
18     cin >> n >> m;
19     cin >> s;
20     for(int i = 0; i < n; i++){
21         cin >> c >> a >> b;
22         mp[c] = min(a, b);//因為增減操作的實質是一樣的 
23     } 
24     for(int j = 0; j < m; j++){
25         for(int i = j-1; i >= 0; i--){//遍歷方式要注意 
26             if(s[i] == s[j]){
27                 dp[i][j] = dp[i+1][j-1];
28             }
29             else{
30                 dp[i][j] = min(dp[i+1][j]+mp[s[i]], dp[i][j-1]+mp[s[j]]);
31             }
32         }
33     }
34     cout << dp[0][m-1] << endl;
35     return 0;
36 }