Palindromic Subsequence
Time Limit: 3000ms
Memory Limit: 131072KB
This problem will be judged on UVA. Original ID: 11404
64-bit integer IO format: %lld Java class name: Main
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 解题:求最长的且字典序最小的回文子序列。把原串逆转,然后与原串求LCS。LCS的的前半部分一定要求的回文序列的前半部分,但是后半部分可能不是。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
struct DP{
int len;
string str;
};
DP dp[maxn][maxn];
char sa[maxn],sb[maxn];
int main() {
while(gets(sa)){
int len = strlen(sa);
strcpy(sb,sa);
reverse(sb,sb+len);
for(int i = ; i <= len; ++i){
dp[][i].len = ;
dp[][i].str = "";
}
for(int i = ; i <= len; ++i){
for(int j = ; j <= len; ++j){
if(sa[i-] == sb[j-]){
dp[i][j].len = dp[i-][j-].len+;
dp[i][j].str = dp[i-][j-].str + sa[i-];
}else if(dp[i-][j].len > dp[i][j-].len){
dp[i][j].len = dp[i-][j].len;
dp[i][j].str = dp[i-][j].str;
}else if(dp[i-][j].len < dp[i][j-].len){
dp[i][j].len = dp[i][j-].len;
dp[i][j].str = dp[i][j-].str;
}else{
dp[i][j].len = dp[i-][j].len;
dp[i][j].str = min(dp[i-][j].str,dp[i][j-].str);
}
}
}
string ans = dp[len][len].str;
if(dp[len][len].len&){
for(int i = ; i < dp[len][len].len>>; ++i)
putchar(ans[i]);
for(int i = dp[len][len].len>>; i >= ; --i)
putchar(ans[i]);
putchar('\n');
}else{
for(int i = ; i+ < dp[len][len].len>>; ++i)
putchar(ans[i]);
for(int i = dp[len][len].len>>; i >= ; --i)
putchar(ans[i]);
putchar('\n');
}
}
return ;
}