题目传送门：https://www.luogu.org/problemnew/show/SP33
题目大意：给出两个字符串，求其LCS（最长公共子序列）的长度与具体方案（相同的串算作同一方案）。数据组数$\leq 10$，字符串长度$\leq 80$，方案数$\leq 1000$
本来以为这是一道LCS水题，结果超级low的各种输出方案的方法TLE到怀疑人生
于是一个高大上的输出方法出现（借鉴于https://blog.csdn.net/gg_gogoing/article/details/41170117）
多开两个辅助数组$f_{i,j}$与$g_{i,j}$代表$s1$与$s2$从第$1$个字符到第$i$个字符中字符$j$（$a$对应$0$，$b$对应$1$，以此类推）最后一次出现的位置，计算完这两个数组之后，进行递归输出，同时使用枚举法，从后往前一个一个枚举当前位置可填的字母。
设$dfs( a , b , c)$表示当前$s1$的长度为$a$，$s2$的长度为$b$，待枚举的字母数量为$c$时的枚举过程，枚举$0-25$，得到该字母的$f_{a,b}$与$g_{a,b}$，如果当$s1$长度为$f_{a,b}$,$s2$长度为$g_{a,b}$时的最长公共子序列长度正好为$c$，则$dfs(f_{a,b} - 1 , g_{a,b} - 1 , c - 1)$，枚举完第一位后即得到一种满足题意的字符串
为何这样子可以大量剪枝？举例：
$abcabcaa$
$acbacba$
上面是样例数据，最长公共子序列长度为$5$。考虑$dfs(7,6,5)$时枚举到$a$（字符串从$0$开始标号），此时$f = 7 , g = 6$，会进行$dfs(6,5,4)$。如果不考虑上述枚举，我们的可选方案有$(0,0)(0,3)(0,6)(3,0)(3,3)(3,6)(6,0)(6,3)(6,6)(7,0)(7,3)(7,6)$共$12$种，因为相同的串算作同一方案，由贪心可以知道$(7,6)$是当前的最优选择，可以包含其他的所有情况，所以只需要向$(7,6)$继续搜索即可。
#include<bits/stdc++.h>
using namespace std;
string s1 , s2;
vector < string > s;
][] , last1[][] , last2[][] , cou;
//last1、last2对应上面的f、g。
inline int max(int a , int b){
return a > b ? a : b;
}
void create(int a1 , int a2 , int num , string ss){
){
s.push_back(ss);
return;
}
; i < ; i++)
if(last1[i][a1] >= num && last2[i][a2] >= num && maxN[last1[i][a1]][last2[i][a2]] == num)
create(last1[i][a1] - , last2[i][a2] - , num - , (char)('a' + i) + ss);
//递归输出最重要的过程！！！
}
int main(){
ios::sync_with_stdio();
int T;
for(cin >> T ; T ; T--){
memset(maxN , , sizeof(maxN));
memset(last1 , , sizeof(last1));
memset(last2 , , sizeof(last2));
cin >> s1 >> s2;
; i <= s1.size() ; i++)
; j <= s2.size() ; j++){
] == s2[j - ]) maxN[i][j] = max(maxN[i][j] , maxN[i - ][j - ] + );
maxN[i][j] = max(maxN[i][j] , max(maxN[i - ][j] , maxN[i][j - ]));
}
//LCS DP求解
; i <= s1.size() ; i++)
; j < ; j++)
] - 'a' == j) last1[j][i] = i;
];
; i <= s2.size() ; i++)
; j < ; j++)
] - 'a' == j) last2[j][i] = i;
];
create(s1.size() , s2.size() , maxN[s1.size()][s2.size()] , "");
sort(s.begin() , s.end());
; i < s.size() ; i++) cout << s[i] << endl;
//输出
s.clear();
cout << endl;
cou = ;
}
;
}