首页 > 代码库 > SRM 509 DIV1 500pt(DP)
SRM 509 DIV1 500pt(DP)
题目简述
给定一个字符串，可以对其进行修改，删除，增加操作，相应的操作有对应的花费，要求你用最小的花费把字符串变为回文串
题目做法
先搞一遍floyed把各种操作的最小花费求出来，然后就是类似编辑距离的DP了，这题坑了好久。。。中间结果会爆int，我设置的inf=0x3f3f3f3f,中间结果有inf+inf+inf..刚开始dp数组是int型的。。。这里搞了好几才发现这问题。。。西安现场赛也遇到这个问题了。。。然后也是浪费了将近100分钟的时间。。。导致后面做题的时间不够了。。。
代码:
1 #define maxn 30 2 int changeCost[maxn][maxn], addCost[maxn], eraseCost[maxn]; 3 LL dp[55][55]; 4 class PalindromizationDiv1 5 { 6 public: 7 int getMinimumCost(string word, vector <string> operations) 8 { 9 memset(changeCost, 0x3f, sizeof(changeCost));10 memset(addCost, 0x3f, sizeof(addCost));11 memset(eraseCost, 0x3f, sizeof(eraseCost));12 for (int i = 0; i < operations.size(); i++)13 {14 stringstream ss(operations[i]);15 string s;16 char a, b;17 int num;18 ss >> s;19 if (s == "add")20 {21 ss >> a >> num;22 addCost[a - ‘a‘] = num;23 }24 if (s == "erase")25 {26 ss >> a >> num;27 eraseCost[a - ‘a‘] = num;28 }29 if (s == "change")30 {31 ss >> a >> b >> num;32 changeCost[a - ‘a‘][b - ‘a‘] = num;33 }34 }35 for (int i = 0; i < 26; i++) changeCost[i][i] = 0;36 for (int k = 0; k < 26; k++)37 for (int i = 0; i < 26; i++)38 for (int j = 0; j < 26; j++)39 {40 if (i == j || j == k || i == k) continue;41 changeCost[i][j] = min(changeCost[i][j], changeCost[i][k] + changeCost[k][j]);42 }43 44 for (int i = 0; i < 26; i++)45 for (int j = 0; j < 26; j++)46 {47 addCost[i] = min(addCost[i], addCost[j] + changeCost[j][i]);48 eraseCost[i] = min(eraseCost[i], changeCost[i][j] + eraseCost[j]);49 }50 int n = word.size();51 memset(dp, 0x3f, sizeof(dp));52 for (int i = n - 1; i >= 0; i--)53 {54 dp[i][i] = dp[i][i - 1] = 0;55 for (int j = i + 1; j < n; j++)56 {57 int a = word[i] - ‘a‘, b = word[j] - ‘a‘;58 dp[i][j] = min(dp[i][j], dp[i + 1][j] + eraseCost[a]);59 dp[i][j] = min(dp[i][j], dp[i][j - 1] + eraseCost[b]);60 for (int k = 0; k < 26; k++)61 {62 dp[i][j] = min(dp[i][j], dp[i + 1][j] + addCost[k] + changeCost[a][k]);63 dp[i][j] = min(dp[i][j], dp[i][j - 1] + addCost[k] + changeCost[b][k]);64 dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + changeCost[a][k] + changeCost[b][k]);65 }66 }67 }68 LL ret = dp[0][n - 1];69 return ret >= INF ? -1 : (int)ret;70 }71 };
SRM 509 DIV1 500pt(DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。