UVA - 11151 Longest Palindrome

本文主要是介绍UVA - 11151 Longest Palindrome，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：以为是求最长回文串，结果用Manacher 一直错，原来题目是求最长回文子串，汗！！那么就很好处理了，跟之前的一样，当str[l]==str[r]的时候，+1，否则在dp(l+1,r),dp(l,r-1)找最大的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1100;int dp[MAXN][MAXN],n;
char str[MAXN];int DP(int l,int r){if (dp[l][r] != -1)return dp[l][r];if (l > r)return 0;if (l == r)return 1;if (str[l] == str[r])dp[l][r] = DP(l+1,r-1) + 2;else dp[l][r] = max(DP(l+1,r),DP(l,r-1));return dp[l][r];
}int main(){int t;scanf("%d%*c",&t);while (t--){memset(dp,-1,sizeof(dp));gets(str);n = strlen(str);cout << DP(0,n-1) << endl;}return 0;
}

这篇关于UVA - 11151 Longest Palindrome的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---