HDU 4745 Two Rabbits——最长回文子串

HDU 4745 Two Rabbits——最长回文子串

这道题实际上是求一个序列的最长回文子串的长度，

这道题的特殊性就在于已知的序列是一个环，我们可以用倍增法将他扩展为一个链，然后求这个链长度为n以内的最长回文子串（大可不用考虑长度为n，只需求这个2*n序列的最长回文子串即可，因为求2*n序列解的过程实际上把前面所有解都求出来了，最后只要循环扫一便找出需要的解就可以，具体参考代码最后两个循环）

因为题目要求不能再经过已经经过的点，所以把最长回文子串的长度作为解有漏洞，如1 2 1 4，他的n以内的最长回文子串是1 2 1，长度为3，实际长度应该为4，出现了错误。

关于这个错误我就不做解释了，这个要自己理解一下，我解释的不周到的话可能会影响大家的思考，这里只给出解决方案：

求出长度为n-1以内的最长回文子串长度，将其 + 1后与原结果进行比较，大的那个即最终结果，具体参考代码最后一个循环

#include #include #include #include using namespace std;const int maxn = 2020;int n, a[maxn], dp[maxn][maxn];int main(){ while (cin >> n && n) { for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i + n] = a[i]; } memset(dp, 0, sizeof(dp)); for (int i = 2 * n; i >= 1; i--) { for (int j = i + 1; j <= 2 * n; j++) { dp[i][i] = 1; if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][i + n - 1]); } for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][i + n - 2] + 1); } printf("%d\n", ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。