| UVA - 11404 |
题意：一个字符串，删去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+;
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=;s="";}
}f[N][N];
void dp(){
for(int i=;i<=n;i++) b[i]=a[n-i+]; for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(a[i]==b[j]){
f[i][j].v=f[i-][j-].v+;
f[i][j].s=f[i-][j-].s+a[i];
}else{
if(f[i][j-].v>f[i-][j].v){
f[i][j].v=f[i][j-].v;
f[i][j].s=f[i][j-].s;
}else if(f[i-][j].v>f[i][j-].v){
f[i][j].v=f[i-][j].v;
f[i][j].s=f[i-][j].s;
}else{
f[i][j].v=f[i][j-].v;
f[i][j].s=min(f[i][j-].s,f[i-][j].s);
}
}
}
}
int main(int argc, const char * argv[]) {
while(scanf("%s",a+)!=EOF){
n=strlen(a+);
dp();
int len=f[n][n].v;
string s=f[n][n].s;
if(len&){
len/=;
for(int i=;i<len;i++) putchar(s[i]);
for(int i=len;i>=;i--) putchar(s[i]);//!
}else{
len/=;
for(int i=;i<len;i++) putchar(s[i]);
for(int i=len-;i>=;i--) putchar(s[i]);
}
putchar('\n');
} return ;
}