题面
给你两个由'a'到'z'组成的字符串，长度均不超过80，按字典序输出它们的所有的最长公共子序列的方案，保证方案数不超过1000。
链接：http://poj.org/problem?id=1934
思路
开始看到这道题时，一想不就是一道暴力吗，用(f_i,_j)按字典序保存A串的前i个字符与B串的前j个字符所组成的所有的最长公共子序列，普通转移时归并维护字符串的顺序，顺带去重，复杂度为O((80^3)*1000)。不过好像是常数太大？所以会超时_。
当你觉得陷入死胡同时，一定不要走到黑。设(S_i,_j)为A串的前i个字符与B串的前j个字符所组成一个公共子序列，对于一个(S_i,_j)，我们考虑它可能转移到的状态，即下一个字母为'a'到'z'。如果要转移到的下一个字母为k，可能有很多个符合条件的点可以转移，那选哪一个呢？假设(nextA_i,_k) 表示离A序列的第i号位最近的且比i大的k字符的位置，(nextB_j,_k)类似，如果下一个字母是k,那么一定是转移到 (S_{{nextA_i,_k},{nextB_i,k}})，因为对于转移到的两个的i与j而言，转移到一对l,r(l>=i,r>=j)一定不会更优，可以用贪心的决策包容性来证明。所以我们预处理(nextA_i,_k)，(nextB_j,_k)。再用dfs(i,j,len,s)表示当前搜到了(S_i,_j)，长度为len的，串为s的一个序列，通过循环'a'-'z'继续搜索，当一个次dfs时26个字母都无法搜下去，那么就更新答案。最后的答案不用排序，不用判重。
但复杂度还是太高，所以我们剪枝。考虑对于最终的一种最优方案，他一定是从子状态的一种最优方案转移来的。所以我们先用dp计算(S_i,_j)的最长长度，如果对于dfs(i,j,len,s)，len小于这个长度时，那么他肯定不能转移到最优答案，所以return。我们巧妙的避开了dp的缺点(不好保存具体方案)，而利用了优点(很好求出最优长度)。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1100;
string ans[N];
int dp[90][90],fa[90][30],fb[90][30],alph[30],maxl=0,cnt;
char a[90],b[90];
string s;
void load(char a[],int fa[][30],int n)
{
memset(alph,0,sizeof(alph));
for(int i=n;i>=1;i--)
{
int k=a[i]-'a'+1;
if(alph[k])
for(int j=i;j<alph[k];j++)
fa[j][k]=alph[k];
alph[k]=i;
}
for(int i=1;i<=26;i++)
if(alph[i])
for(int j=0;j<alph[i];j++)
fa[j][i]=alph[i];
}
void updata(int len)
{
if(len<maxl) return;
if(len>maxl) cnt=0,maxl=len;
ans[++cnt]=s;
}
void dfs(int l,int r,int len)
{
int ll,rr,k=0;
for(int i=1;i<=26;i++)
{
ll=fa[l][i],rr=fb[r][i];
if(!ll||!rr||dp[ll][rr]>len+1) continue;
k=1;
s.insert(s.end(),1,'a'+i-1);
dfs(ll,rr,len+1);
s.erase(s.end()-1);
}
if(!k) updata(len);
}
int main()
{
scanf("%s%s",a+1,b+1);
int n=strlen(a+1),m=strlen(b+1);
load(a,fa,n);load(b,fb,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
}
dfs(0,0,0);
for(int i=1;i<=cnt;i++)
cout<<ans[i]<<endl;
return 0;
}