首页 > 代码库 > UVA 11404 Palindromic Subsequence
UVA 11404 Palindromic Subsequence
Palindromic Subsequence
Time Limit: 3000ms
Memory Limit: 131072KB
This problem will be judged on UVA. Original ID: 1140464-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
aabbaabbcomputerabzlasamhita
Sample Output
aabbaacabaaha
解题：求最长的且字典序最小的回文子序列。把原串逆转，然后与原串求LCS。LCS的的前半部分一定要求的回文序列的前半部分，但是后半部分可能不是。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 1010;18 struct DP{19 int len;20 string str;21 };22 DP dp[maxn][maxn];23 char sa[maxn],sb[maxn];24 int main() {25 while(gets(sa)){26 int len = strlen(sa);27 strcpy(sb,sa);28 reverse(sb,sb+len);29 for(int i = 0; i <= len; ++i){30 dp[0][i].len = 0;31 dp[0][i].str = "";32 }33 for(int i = 1; i <= len; ++i){34 for(int j = 1; j <= len; ++j){35 if(sa[i-1] == sb[j-1]){36 dp[i][j].len = dp[i-1][j-1].len+1;37 dp[i][j].str = dp[i-1][j-1].str + sa[i-1];38 }else if(dp[i-1][j].len > dp[i][j-1].len){39 dp[i][j].len = dp[i-1][j].len;40 dp[i][j].str = dp[i-1][j].str;41 }else if(dp[i-1][j].len < dp[i][j-1].len){42 dp[i][j].len = dp[i][j-1].len;43 dp[i][j].str = dp[i][j-1].str;44 }else{45 dp[i][j].len = dp[i-1][j].len;46 dp[i][j].str = min(dp[i-1][j].str,dp[i][j-1].str);47 }48 }49 }50 string ans = dp[len][len].str;51 if(dp[len][len].len&1){52 for(int i = 0; i < dp[len][len].len>>1; ++i)53 putchar(ans[i]);54 for(int i = dp[len][len].len>>1; i >= 0; --i)55 putchar(ans[i]);56 putchar(‘\n‘);57 }else{58 for(int i = 0; i+1 < dp[len][len].len>>1; ++i)59 putchar(ans[i]);60 for(int i = dp[len][len].len>>1; i >= 0; --i)61 putchar(ans[i]);62 putchar(‘\n‘);63 }64 }65 return 0;66 }
UVA 11404 Palindromic Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。