首页 > 代码库 > POJ 3280 Cheapest Palindrome DP题解
POJ 3280 Cheapest Palindrome DP题解
看到Palindrome的题目,首先想到的应该是中心问题,然后从中心出发,思考如何解决。
DP问题一般是从更加小的问题转化到更加大的问题,然后是从地往上 bottom up地计算答案的。
能得出状态转移方程就好办了,本题的状态转移方程是:
if (cowID[i] == cow{j]) tbl[id][i] = tbl[id][i+1];//相等的时候无需改动
else tbl[id][i] = min(tbl[!id][i+1] + cost[cowID[i]-‘a‘], tbl[!id][i] + cost[cowID[j]-‘a‘]);//不相等的时候需要看改动那一边的字符比较划算
注意:
1 cost的删除和插入对于DP来说实际是一样的操作,所以只需要报出一个最小的cost就可以了
2 cost的值是以字母为下标保存值的,不是按顺序给出的,也可能某些字母的值没有给出,这个时候默认应该为零
最后是需要节省内存,这些题目一般可以只看一维dp table数组就可以了,这个时候要二维转化为一维保存结果,实际测试内存节省非常多。
这里使用所谓的滚动数组,轮流使用两个数组记录数据。
主要把二维表的斜对角格转为一个数组保存,对应好下标就可以了。
#include <stdio.h> #include <string.h> const int MAX_M = 2001; const int MAX_N = 26; char cowID[MAX_M]; int cost[MAX_N];//minimum of the cost of adding and deleting that character. int tbl[2][MAX_M]; int N, M; inline int min(int a, int b) { return a < b ? a : b; } int getMinCost() { memset(tbl[0], 0, sizeof(int)*M); memset(tbl[1], 0, sizeof(int)*M); bool id = false; for (int d = 2; d <= M; d++) { id = !id; for (int i = 0, j = d-1; j < M; i++, j++) { if (cowID[i] == cowID[j]) tbl[id][i] = tbl[id][i+1]; else { int c1 = tbl[!id][i+1] + cost[cowID[i]-'a']; int c2 = tbl[!id][i] + cost[cowID[j]-'a']; tbl[id][i] = min(c1, c2); } } } return tbl[id][0]; } int main() { char a; int c1, c2; while (scanf("%d %d", &N, &M) != EOF) { memset(cost, 0, sizeof(int)*N); getchar(); gets(cowID); for (int i = 0; i < N; i++) { a = getchar(); scanf("%d %d", &c1, &c2); cost[a-'a'] = min(c1, c2);//only need to save the minimum getchar(); } printf("%d\n", getMinCost()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。