题意：
求最长公共子序列，并且这个子序列是字典序最小。
思路：
LCS附一个值,dp[i][j].first代表以i，j的LCS的长度，dp[i][j].second代表LCS结尾元素，然后利用路径输出就好了；
竖着传就是1，横着就是-1，斜对角就是0；
然后就wa掉了。。。因为单一的判断结尾肯定不行啊，要判断这个满足的串；
138885777
15738
所以second为整个串；所以不需要路径记录了；
直接输出dp[L1][L2].second就好了；
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; const int N=1e2+10;
const int INF=0x3f3f3f3f; int len1,len2;
char s1[N],s2[N];
struct asd{
int first;
string second;
};
asd dp[N][N]; void LCS()
{
for(int i=0;i<=len1;i++)
for(int j=0;j<=len2;j++)
{
dp[i][j].first=0;
dp[i][j].second="";
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(s1[i]==s2[j])
{
dp[i][j].first=dp[i-1][j-1].first+1;
dp[i][j].second=dp[i-1][j-1].second;
dp[i][j].second+=s1[i];
}
else
{
if(dp[i-1][j].first>dp[i][j-1].first)
{
dp[i][j].first=dp[i-1][j].first;
dp[i][j].second=dp[i-1][j].second;
}
else if(dp[i-1][j].first<dp[i][j-1].first)
{
dp[i][j].first=dp[i][j-1].first;
dp[i][j].second=dp[i][j-1].second;
}
else if(dp[i-1][j].first==dp[i][j-1].first)
{
if(dp[i-1][j].second<dp[i][j-1].second)
{
dp[i][j].first=dp[i-1][j].first;
dp[i][j].second=dp[i-1][j].second;
}
else
{
dp[i][j].first=dp[i][j-1].first;
dp[i][j].second=dp[i][j-1].second;
}
}
}
}
}
if(!dp[len1][len2].first)
{
printf(":(\n");
return;
}
cout<<dp[len1][len2].second<<endl;
} int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",s1+1,s2+1);
len1=strlen(s1+1);
len2=strlen(s2+1);
printf("Case %d: ",cas++);
LCS();
}
return 0;
}