Trip

我不是女神ヾ 2022-01-08 00:29 165阅读 0赞

[Trip][]

给出一个长度为n序列\\(\\\{a\_i\\\}\\)，长度为m的序列\\(\\\{b\_i\\\}\\)，求它们的不同lcs序列按字典序输出，\\(n,m\\leq 80\\)，lcs不超过1000个，字符为26个小写字母。

### 解 ###

注意，按照传统思路，递推+暴力方案转移+归并排序，时间复杂度\\(O(80^3 \\times 1000)=O(512000000)=O(5.12\\times 10^8)\\)，必然会超时，而数据范围又很小，考虑dfs，并用递推的结果优化dfs。

为了让递推结果\\(f\[i\]\[j\]\\)表示a序列前i长度，b序列前j长度的最长lcs能起作用，必然是从后往前搜，如果当前的状态能提供的lcs加上已经确定lcs不能为最优解的话，可以剪枝，另外，为了快速确定相同的字符，我们维护\\(fa\[i\]\[j\]\\)表示a序列字符i的在\\(1\\sim j\\)的最靠后的位置，fb同理，不难有

\\\[fa\[i\]\[j\]=\\max(fa\[i\]\[j-1\],j(a\[j\]==i+96))\\\]

于是维护出这两个东西，以此来dfs剪枝，就可以有很高的效率，不至于tle了。

参考代码：

#include <iostream> #include <cstdio> #include <string> #include <algorithm> #define il inline #define ri register using namespace std; string a,b,ans[2050]; int dp[101][101],fa[101][101], fb[101][101],tot,len; il int max(int,int); void dfs(int,int,string),work(); int main(){ int lsy;cin>>lsy; while(lsy--)work(),putchar('\n'); return 0; } void work(){ cin>>a>>b,tot&=0; for(int i(1),j;i<=a.size();++i) for(j=1;j<=b.size();++j){ dp[i][j]=max(dp[i][j-1],dp[i-1][j]); if(a[i-1]==b[j-1])dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]); } for(int i(1),j;i<=26;++i){ for(j=1;j<=a.size();++j) if(a[j-1]==i+96)fa[i][j]=j; else fa[i][j]=fa[i][j-1]; for(j=1;j<=b.size();++j) if(b[j-1]==i+96)fb[i][j]=j; else fb[i][j]=fb[i][j-1]; }len=dp[a.size()][b.size()]; dfs(a.size(),b.size(),""),sort(ans+1,ans+tot+1); for(int i(1);i<=tot;++i)cout<<ans[i]<<endl; } void dfs(int a,int b,string s){ if(a<0||b<0)return; if(s.size()==len)return(void)(ans[++tot]=s); for(int i(1);i<=26;++i) if(dp[fa[i][a]][fb[i][b]]+s.size()==len) dfs(fa[i][a]-1,fb[i][b]-1,(char)(i+96)+s); } il int max(int a,int b){ return a>b?a:b; }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10995765.html

[Trip]: https://www.luogu.org/problemnew/show/SP33