首页 > 代码库 > uva10453 - Make Palindrome(递推+ 路径输出)
uva10453 - Make Palindrome(递推+ 路径输出)
题目:uva10453 - Make Palindrome(递推+ 路径输出)
题目大意:给出一字符串,仅仅只能做增加字符的操作,问最少增加多少字符串可以是的最后的字符串变成回文。并且将这样的字符串(增加长度要是最小的)的任意一种输出。
解题思路:dp【i】【j】代表第i个字符到第j个字符之间要增加的最少的字符串。递推公式:s【i】 == s【j】, dp【i】【j】 = dp【 i + 1】【j - 1】; s【i】 != s【j】 ,dp【i][j] = min (dp[i + 1][j] + 1, dp
[i][j - 1] + 1,dp[i + 1][j - 1] + 2);
路径输出就是用递归的思想,从后往前找对应的路径,因为是回文,所以这里只存字符串的一半在ans中,长度为奇数的回文中间的那个字符也要存下来。
代码:
#include <cstdio> #include <cstring> const int N = 1005; int dp[N][N]; char str[N]; char ans[N]; void init (int len) { for (int i = 0; i < len; i++) { dp[i][i] = 0; if (i + 1 < len) { if (str[i] == str[i + 1]) dp[i][i + 1] = 0; else dp[i][i + 1] = 1; } } } int Min (const int a, const int b) { return a < b ? a: b; } void printf_ans (int i, int j) { if (i == j) { ans[0] = str[i]; } else if (j - i == 1) { if (str[i] == str[j]) { ans[0] = str[i]; } else { ans[0] = str[j]; ans[1] = str[i]; } } else { int len = (j - i + dp[i][j]) / 2 + 1; if (str[i] == str[j]) { printf_ans(i + 1, j - 1); ans[len - 1] = str[i]; } else { if (dp[i][j] == dp[i + 1][j] + 1) { printf_ans(i + 1, j); ans[len - 1] = str[i]; } else if (dp[i][j] == dp[i][j - 1] + 1) { printf_ans(i, j - 1); ans[len - 1] = str[j]; } else { printf_ans(i + 1, j - 1); ans[len - 2] = str[j]; ans[len - 1] = str[i]; } } } } int main () { int len; while (gets(str) != NULL) { len = strlen (str); if (!len) { printf ("0 %s\n", str); continue; } init (len); for (int n = 3; n <= len; n++) { for (int i = 0, j = n - 1; j < len; i++, j++) { if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = Min (dp[i + 1][j - 1] + 2, Min (dp[i][j - 1],dp[i + 1][j]) + 1); } } printf ("%d ", dp[0][len - 1]); if (dp[0][len - 1] == 0) printf ("%s\n", str); else { printf_ans(0, len - 1); len += dp[0][len - 1]; if (len % 2) { len /= 2; for (int i = len; i > 0; i--) printf ("%c", ans[i]); } else { len = len / 2 - 1; for (int i = len; i >= 0; i--) printf ("%c", ans[i]); } ans[len + 1] = '\0'; printf ("%s\n", ans); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。