|
题意:一个字符串,删去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#include #include #include 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 =0;i--) putchar(s[i]);//! }else{ len/=2; for(int i=0;i =0;i--) putchar(s[i]); } putchar('\n'); } return 0;}