https://vjudge.net/problem/POJ-3280
猛刷简单dp第一天第三题。
这个据说是【求字符串通过增减操作变成回文串的最小改动次数】的变体。
首先增减操作的实质是一样的，所以输入时求min。
dp[i][j]表示第i个字符到第j个字符中修改成回文串的最小代价。由于回文串的特殊性，这里两层循环的遍历方式跟常见的略有不同
这算是回文串dp的一种典型题目典型方法吧。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int n, m, a, b, dp[][];
map<char, int> mp;
char s[], c;
int main()
{
cin >> n >> m;
cin >> s;
for(int i = ; i < n; i++){
cin >> c >> a >> b;
mp[c] = min(a, b);//因为增减操作的实质是一样的
}
for(int j = ; j < m; j++){
for(int i = j-1; i >= ; i--){//遍历方式要注意
if(s[i] == s[j]){
dp[i][j] = dp[i+][j-];
}
else{
dp[i][j] = min(dp[i+][j]+mp[s[i]], dp[i][j-]+mp[s[j]]);
}
}
}
cout << dp[][m-] << endl;
return ;
}