1040 Longest Symmetric String (25分)
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply print the maximum length in a line.
Sample Input:
Is PAT&TAP symmetric?
Sample Output:
11
本题思路：区间dp的思想，不过区间dp一般还枚举区间中间的状态量，而此题由于是回文，当中间不是回文串的时候直接不考虑，中间是回文串则直接长度增加，相对较简单。
当然此题也可以用马拉车和暴力AC。但显得不够优雅/xyx
1 #include <iostream> 2 #include <string> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 1000 + 5; 7 8 int dp[maxn][maxn]; 9 10 int main() { 11 for(int i = 0; i < maxn; i ++) { 12 dp[i][i] = 1; 13 } 14 string s; 15 getline(cin, s); 16 int n = s.length(); 17 int ans = 1; 18 for(int len = 1; len < n; len ++) { 19 for(int i = 0; i < n - 1; i ++) { 20 int j = i + len; 21 if(s[i] == s[j]) { 22 if(len == 1) { 23 dp[i][j] = 2; 24 } else if(dp[i + 1][j - 1] > 0) { 25 dp[i][j] = 2 + dp[i + 1][j - 1]; 26 } 27 ans = max(ans, dp[i][j]); 28 } 29 } 30 } 31 cout << ans << endl; 32 return 0; 33 }