1040 Longest Symmetric String (25分)（dp）

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[i]=前i个字符中最大的对称字串$

$dp[i]=\begin{cases}dp[i]=max(dp[i],dp[i-1]+2),& \text{if}\ s[i-1]=s[i-dp[i-1]-2] \\ dp[i]=max(dp[i],dp[i-1]+1), & \text{if}\ s[i-1]=s[i-dp[i-1]-1] \end{cases}$

$估计这也并不好理解其实可以这么想对于每一个dp[i]来说我们更新它只有两种方式，一种是在dp[i-1]的基础上加两个字符分别是第i-1个字符与 i-dp[i-1]-2字符（不难算) 一种是在dp[i-1]的基础上只加第i-1个元素$

 #define _CRT_SECURE_NO_WARNINGS

 #include <climits>

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<map>

 #include<set>

 #include<stack>

 #include<algorithm>

 #include<string>

 #include<cmath>

 using namespace std;

 int dp[]; //dp[i]定义为前i个字符中最大对称字串

 int main()

 {

     string s;

     getline(cin, s);

     for (int i = ; i <= s.length(); i++)

     {

         if (i - dp[i - ] -  >= )

             if (s[i - ] == s[i - dp[i - ] - ])

                 dp[i] =max(dp[i],dp[i - ] + );

         if (i - dp[i - ] -  >= )

             if (s[i - ] == s[i - dp[i - ] - ])

                 dp[i] = max(dp[i], dp[i - ] + );

         dp[i] = max(dp[i], );

     }

     int max = -;

     for (int i = ; i <= s.length(); i++)

     {

         if (dp[i] > max)

             max = dp[i];

     }

     cout << max;

 }

巴特西

1040 Longest Symmetric String (25分)（dp）

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章