这题是最长公共子序列的变形，要注意的就是，题目要求输出最长上升子序列的字典排序最小值，最麻烦的就是这个，想了半天都没什么思路，我对最长上升子序列的理解不是很透彻。在网上看了别人的题解，都是用一个结构题来保存状态 （公共子序列的长度，公共子序列的串）我才恍然大悟，既然这样，那不是搜索一遍所有的状态的字符串就可以了吗。
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN 1010
struct Node
{
int l;
string s;
}no[MAXN][MAXN];
char sm[MAXN];
int main()
{
while(scanf("%s",sm)==1)
{
string s1=sm;
int len=s1.length();
string s2="";
for(int i=len-1,k=0;i>=0;i--,k++)
{
s2+=s1[i];
}
// cout<<s2<<endl;
s1='*'+s1;
s2='*'+s2;
for(int i=0;i<=len;i++)//初始化
{
no[0][i].l=0;no[0][i].s="";
}
for(int i=1;i<=len;i++)
{
for(int j=1;j<=len;j++)
{
if(s1[i]==s2[j])
{
no[i][j].l=no[i-1][j-1].l+1;
no[i][j].s=no[i-1][j-1].s+s1[i];
}
else
{
if(no[i][j-1].l>no[i-1][j].l)
{
no[i][j].l=no[i][j-1].l;
no[i][j].s=no[i][j-1].s;
}
else if(no[i-1][j].l>no[i][j-1].l)
{
no[i][j].l=no[i-1][j].l;
no[i][j].s=no[i-1][j].s;
}
else if(no[i-1][j].l==no[i][j-1].l)
{
no[i][j].l=no[i-1][j].l;
if(no[i-1][j].s<no[i][j-1].s)
{
no[i][j].s=no[i-1][j].s;
}
else no[i][j].s=no[i][j-1].s;
}
}
}
}
int maxl=no[len][len].l;
string str=no[len][len].s;
string ans="";
// for(int i=1;i<=len;i++)
// {
// for(int j=1;j<=len;j++)
// {
// cout<<"i: "<<i<<' '<<"j: "<<j<<' '<<no[i][j].l<<' '<<no[i][j].s<<endl;
// }
// }
if(maxl&1)
{
for(int i=0;i<maxl/2;i++)
{
ans+=str[i];
}
for(int i=maxl/2;i>=0;i--)
{
ans+=str[i];
}
}
else
{
for(int i=0;i<maxl/2;i++)
{
ans+=str[i];
}
for(int i=maxl/2-1;i>=0;i--)
{
ans+=str[i];
}
}
cout<<ans<<endl;
}
}