问题描述：最长公共子序列问题 • 输入：第一行：随机产生序列A（m个字符）；随机 产生序列B（m个字符） • 输出：序列A和序列B的最长公共子序列 例如输入的A为wehty，B为wekty，得到的输出为wety 使用穷举法，要求用二进制数表示每一个字符是否在子序列中，C++

++代码如下：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

vector<string> lcs(string A, string B){
int m = A.size(), n = B.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// dp[i][j]表示A[0...i-1]和B[0...j-1]的最长公共子序列长度
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
vector<string> res;
vector<int> indices(m+n); // indices表示选中的字符的下标
int i = m, j = n, k = dp[m][n]-1;
while(i > 0 && j > 0){
if(A[i-1] == B[j-1]){
indices[k--] = i-1;
i--;
j--;
}
else if(dp[i-1][j] > dp[i][j-1]){
i--;
}
else{
j--;
}
}
for(int i = 0; i < (1 << dp[m][n]); i++){
string seq;
int idx = 0;
for(int j = 0; j < m+n; j++){
if(i & (1 << j)){
if(find(indices.begin(), indices.end(), j) != indices.end()){
seq += A[indices[idx++]];
}
else{
seq += B[j-idx];
}
}
}
res.push_back(seq);
}
return res;
}

int main(){
string A, B;
cin >> A >> B;
vector<string> res = lcs(A, B);
cout << "Longest Common Subsequence:" << endl;
for(string seq : res){
cout << seq << endl;
}
return 0;
}

对于输入的随机产生的序列A和B（长度均为m），程序可以输出它们的最长公共子序列。其中，穷举法用二进制数来表示每个字符在子序列中是否出现，总共有2^(最长公共子序列长度)种情况。程序中首先使用动态规划求出最长公共子序列的长度，同时维护一个indices数组记录选中的字符的下标。然后遍历所有的二进制数，根据每个数中1的位置来构造子序列，其中，选中的字符从indices中获取，未选中的字符从B中获取。最终，输出所有的子序列即为所求。