旅行

裸的LCS问题。求长度并不困难，困难的是如何输出所有方案

所以这道题目可以作为DP输出方案的一道典型题目记住

我们一般的方法是记住当前状态是由哪个状态转移过去的，然后逐步递归输出

下面的代码的\(work\)表示两个串分别的前\(x\)个，前\(y\)个，LCS还剩下\(l\)个字符的所有方案（这里要用记忆化，不然的话会MLE或者TLE）

void work(int x,int y,int l)
{
    if(flag[x][y]) return;
	if(!l)
	{
	    G[x][y].push_back("");//G[x][y]表示两个串分别的前x个，前y个能够组成的LCS的所有子串
		return;
	}//如果所有字符都枚举完了就可以直接返回
	string temp;
	map<string,bool> mark;//去重标记
	if(s1[x-1]==s2[y-1])//一种转移
	{
		work(x-1,y-1,l-1);
		int p=G[x-1][y-1].size();
		for(int i=0;i<p;i++)
		{
			temp=G[x-1][y-1][i];
			temp+=s1[x-1];
			G[x][y].push_back(temp);
			mark[temp]=1;
		}
		return;//这里能返回的原因就是因为题目不要求输出重复的子串
	}
	if(f[x-1][y]==l)//一种转移
	{
		work(x-1,y,l);
		int p=G[x-1][y].size();
		for(int i=0;i<p;i++)
		{
			temp=G[x-1][y][i];
			if(mark.find(temp)!=mark.end()) continue;
			G[x][y].push_back(temp);
			mark[temp]=1;
		}
	}
	if(f[x][y-1]==l)//一种转移
	{
		work(x,y-1,l);
		int p=G[x][y-1].size();
		for(int i=0;i<p;i++)
		{
			temp=G[x][y-1][i];
			if(mark.find(temp)!=mark.end()) continue;
			G[x][y].push_back(temp);
			mark[temp]=1;
		}
	}
	flag[x][y]=1;
}

当然这道题目还有一种特殊的做法：我们枚举LCS当前长度的字符是什么。

首先看一下dfs状态

dfs(int x, int y, int k) 在\(a\)的前\(x\)个字符,\(b\)的前\(y\)个字符找LCS中的第\(k\)个字符

我们发现，当选择的字符一样时, 选择字符的位置越靠近\(x\),\(y\)越优（因为题目不要求输出重复的子串）,所以直接找距离\(x\),\(y\)最近的字符\(a\)的位置即可

void dfs(int x, int y, int k)
{
    if (k == 0) { ve.pb(string(ans + 1)); return; }
    for (int i = 0; i < 26; ++i)//枚举当前字符是什么
    {
        int a = fa[x][i], b = fb[y][i];
        if (a < k || b < k || f[a][b] != k) continue;
        ans[k] = 'a' + i;
        dfs(a - 1, b - 1, k - 1);
    }
}