首页 > 代码库 > UVA 11404 Palindromic Subsequence[DP LCS 打印]
UVA 11404 Palindromic Subsequence[DP LCS 打印]
| UVA - 11404 Palindromic Subsequence |
题意：一个字符串，删去0个或多个字符，输出字典序最小且最长的回文字符串
不要求路径区间DP都可以做
然而要字典序最小
倒过来求LCS，转移同时维护f[i][j].s为当前状态字典序最小最优解
f[n][n].s的前半部分一定是回文串的前半部分(想想就行了)
当s的长度为奇时要多输出一个(因为这样长度+1，并且字典序保证最小(如axyzb bzyxa，就是axb))
//// main.cpp// uva11404//// Created by Candy on 03/11/2016.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=1e3+5;char a[N],b[N];int n;//void dp(){// n=strlen(a+1);// ans=0;// //for(int i=1;i<=n;i++) f[i][i]=1;// for(int i=n;i>=1;i--){// f[i][i]=1;// for(int j=i+1;j<=n;j++){// f[i][j]=max(f[i+1][j],f[i][j-1]);// if(a[i]==a[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+1);// }// }//}struct data{ int v; string s; data(){v=0;s="";}}f[N][N];void dp(){ for(int i=1;i<=n;i++) b[i]=a[n-i+1]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(a[i]==b[j]){ f[i][j].v=f[i-1][j-1].v+1; f[i][j].s=f[i-1][j-1].s+a[i]; }else{ if(f[i][j-1].v>f[i-1][j].v){ f[i][j].v=f[i][j-1].v; f[i][j].s=f[i][j-1].s; }else if(f[i-1][j].v>f[i][j-1].v){ f[i][j].v=f[i-1][j].v; f[i][j].s=f[i-1][j].s; }else{ f[i][j].v=f[i][j-1].v; f[i][j].s=min(f[i][j-1].s,f[i-1][j].s); } } }}int main(int argc, const char * argv[]) { while(scanf("%s",a+1)!=EOF){ n=strlen(a+1); dp(); int len=f[n][n].v; string s=f[n][n].s; if(len&1){ len/=2; for(int i=0;i<len;i++) putchar(s[i]); for(int i=len;i>=0;i--) putchar(s[i]);//! }else{ len/=2; for(int i=0;i<len;i++) putchar(s[i]); for(int i=len-1;i>=0;i--) putchar(s[i]); } putchar(‘\n‘); } return 0;}
UVA 11404 Palindromic Subsequence[DP LCS 打印]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。