程序员人生 网站导航

UVa11404Palindromic Subsequence(最大回文串,区间DP)

栏目:php教程时间:2015-06-09 08:29:28
UVa11404Palindromic Subsequence(最大回文串,区间DP)

Description

A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.


Constraints

  • Maximum length of string is 1000.
  • Each string has characters `a' to `z' only.

Input 

Input consists of several strings, each in a separate line. Input is terminated by EOF.

Output 

For each line in the input, print the output in a single line.

Sample Input 

aabbaabb
computer
abzla
samhita

Sample Output 

aabbaa
c
aba
aha

题意:
给定1个字符串s,对s进行删除操作,使得剩下的子串是回文字符串,输出最长的字符串,当有多个相同长度的就输出字典序最小的。
思路:
由于要输出字符串,所以在状态转移进程中要保存下字符串,用C++的string就方便很多,然后就是和找最长回文的方法1样了。
定义结构体保存长度,和字符串,分别用len, s 表示
状态的转移方程为,如果头尾相同,dp[i][j].len = dp[i + 1][j - 1].len + 2(长度加上首尾,所以增加2);如果首尾不同,那末回文长度不增加 dp[i][j].len = max(dp[i + 1][j].len, dp[i][j - 1].len);
如果长度相同  dp[i + 1][j].len, == dp[i][j - 1].len,那末就要比较子串的字典序,取字典序小的,
也就是判断 dp[i + 1][j].s,  dp[i][j - 1].s。

<span style="font-size:18px;">#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <queue> #include <stack> using namespace std; const double PI = acos(⑴.0); const double e = 2.718281828459; const double eps = 1e⑻; const int MAXN = 1010; struct str { int len; string s; } dp[MAXN][MAXN]; char s[MAXN]; int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while(scanf("%s", s+1) != EOF) { int len = strlen(s+1); for(int i = 1; i <= len; i++) { //初始化 dp[i][i].len = 1; dp[i][i].s = s[i]; } for(int k = 2; k <= len; k++) //控制区间大小 { for(int i = 1, j = k; j <= len; i++, j++) //正推 //for(int i = len-k+1, j = len; i >= 1; i--, j--) //逆推 { if(s[i] == s[j]) { dp[i][j].len = dp[i+1][j⑴].len+2; dp[i][j].s = s[i]+dp[i+1][j⑴].s+s[j]; } else { if(dp[i][j⑴].len > dp[i+1][j].len || (dp[i][j⑴].len==dp[i+1][j].len&&dp[i][j⑴].s<dp[i+1][j].s)) { //当 [i, j⑴] 的长度大于 [i+1, j] 的长度,或2者长度相等并且 //[i, j⑴] 的字典序小于 [i+1, j] 的字典序,则选择 [i, j⑴],否则选择后者 dp[i][j].len = dp[i][j⑴].len; dp[i][j].s = dp[i][j⑴].s; } else { dp[i][j].len = dp[i+1][j].len; dp[i][j].s = dp[i+1][j].s; } } } } cout<<dp[1][len].s<<endl; } return 0; } </span>



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐