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 }
?