首页 > 代码库 > uva11151Longest Palindrome(递推)
uva11151Longest Palindrome(递推)
题目;uva11151Longest Palindrome(递推)
题目大意:给出一个字符串,问它可以通过去掉些字符得到的最长的回文的长度。
解题思路:dp【i】【j】代表从字符串i位到j位最长的回文的长度。
如果s【i】 == s【j】 , dp【i】【j】 = dp【i - 1】【j - 1】 + 2; 因为头尾相同,那么要求i到j的最长的回文的话,只有可能是中间的部分最长的回文加上2。
否则dp【i】【j】 = Max (dp【i】【j - 1】, dp【i + 1】【j】);
计算顺序:每次都算固定长度,长度从小到大。注意:有空串的情况。
代码:
#include <cstdio> #include <cstring> const int N = 1005; int dp[N][N]; char str[N]; void init (int len) { for (int i = 0; i < len; i++) { dp[i][i] = 1; if (i + 1 < len) { if (str[i] == str[i + 1]) dp[i][i + 1] = 2; else dp[i][i + 1] = 1; } } } int Max (const int a, const int b) { return a > b ? a: b; } int main () { int cas; int len; scanf ("%d%*c", &cas); while (cas--) { gets(str); len = strlen (str); if (!len) { printf ("0\n"); 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] + 2; else dp[i][j] = Max (dp[i + 1][j], dp[i][j - 1]); } } printf ("%d\n", dp[0][len - 1]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。