给定一个字符串，可以对其进行修改，删除，增加操作，相应的操作有对应的花费，要求你用最小的花费把字符串变为回文串
题目做法
先搞一遍floyed把各种操作的最小花费求出来，然后就是类似编辑距离的DP了，这题坑了好久。。。中间结果会爆int，我设置的inf=0x3f3f3f3f,中间结果有inf+inf+inf..刚开始dp数组是int型的。。。这里搞了好几才发现这问题。。。西安现场赛也遇到这个问题了。。。然后也是浪费了将近100分钟的时间。。。导致后面做题的时间不够了。。。
代码:
#define maxn 30
int changeCost[maxn][maxn], addCost[maxn], eraseCost[maxn];
LL dp[][];
class PalindromizationDiv1
{
public:
int getMinimumCost(string word, vector <string> operations)
{
memset(changeCost, 0x3f, sizeof(changeCost));
memset(addCost, 0x3f, sizeof(addCost));
memset(eraseCost, 0x3f, sizeof(eraseCost));
for (int i = ; i < operations.size(); i++)
{
stringstream ss(operations[i]);
string s;
char a, b;
int num;
ss >> s;
if (s == "add")
{
ss >> a >> num;
addCost[a - 'a'] = num;
}
if (s == "erase")
{
ss >> a >> num;
eraseCost[a - 'a'] = num;
}
if (s == "change")
{
ss >> a >> b >> num;
changeCost[a - 'a'][b - 'a'] = num;
}
}
for (int i = ; i < ; i++) changeCost[i][i] = ;
for (int k = ; k < ; k++)
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
{
if (i == j || j == k || i == k) continue;
changeCost[i][j] = min(changeCost[i][j], changeCost[i][k] + changeCost[k][j]);
} for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
{
addCost[i] = min(addCost[i], addCost[j] + changeCost[j][i]);
eraseCost[i] = min(eraseCost[i], changeCost[i][j] + eraseCost[j]);
}
int n = word.size();
memset(dp, 0x3f, sizeof(dp));
for (int i = n - ; i >= ; i--)
{
dp[i][i] = dp[i][i - ] = ;
for (int j = i + ; j < n; j++)
{
int a = word[i] - 'a', b = word[j] - 'a';
dp[i][j] = min(dp[i][j], dp[i + ][j] + eraseCost[a]);
dp[i][j] = min(dp[i][j], dp[i][j - ] + eraseCost[b]);
for (int k = ; k < ; k++)
{
dp[i][j] = min(dp[i][j], dp[i + ][j] + addCost[k] + changeCost[a][k]);
dp[i][j] = min(dp[i][j], dp[i][j - ] + addCost[k] + changeCost[b][k]);
dp[i][j] = min(dp[i][j], dp[i + ][j - ] + changeCost[a][k] + changeCost[b][k]);
}
}
}
LL ret = dp[][n - ];
return ret >= INF ? - : (int)ret;
}
};