当前位置: 首页 > news >正文

SP33 TRIP - Trip 个人题解

题目链接

题目大意:

给出两个字符串,要求求出所有 LCS (最长公共子序列问题)的具体方案,并按字典序输出

解题方法:

首先我们要清楚求 LCS 的长度的方法,按照闫氏DP分析法我们得到一下过程:

但是我们如果直接在此基础上进行 dfs 查找方案还是会超时,因为本质上是在枚举符合 LCS 长度每一种方案,我们可以用两个数组 \(fa[i][j]\)\(fb[i][j]\) 分别来处理字符串 \(a\) 与字符串 \(b\) 在讨论方案问题的位置,再进行 dfs 回溯查找。

数组 \(fa[i][j]\) 表示字符串 \(a\)\(i\) 个字符中字母 \(j+'a'\) 最近出现的位置,即:\(\begin{cases}if(a[i]==j+'a')&fa[i][j]=i;\\ else&fa[i][j]=fa[i-1][j];\end{cases}\)

同理,数组\(fb[i][j]\) 表示字符串 \(b\)\(i\) 个字符中字母 \(j+'a'\) 最近出现的位置,即:\(\begin{cases}if(a[i]==j+'a')&fb[i][j]=i;\\ else&fb[i][j]=fb[i-1][j];\end{cases}\)

然后我们看一下 dfs 求方案的状态,我们用 dfs(int x,int y,int k) 来表示在字符串 \(a\) 的前 \(x\) 个字符,字符串 \(b\) 的前 \(y\) 个字符找第 \(k\) 个字符的状态,我们发现当选择的字符一致时,越靠近第 \(x\) 个字符和第 \(y\) 个字符的位置越优,且可以包含后面同样时相同字符时的情况,所以我们在查找第 \(k\) 个字符时直接找距离第 \(x\) 个字符和第 \(y\) 个字符最近的字符 \(a\) 的位置即可,时间复杂度玄学,但能过(

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=101;
char a[N],b[N],ch[N];
int f[N][N],fa[N][26],fb[N][26];
vector<string> ans;
inline void dfs(int x,int y,int k){//求方案 if(!k){//如果全部查询完,将答案存放在ans里 string s=string(ch+1);ans.push_back(s);return; }for(int j=0;j<26;j++){//寻找最近的字符 int xa=fa[x][j],xb=fb[y][j];if(xa<k || xb<k || f[xa][xb]!=k) //如果超出范围调出 continue;ch[k]=j+'a';dfs(xa-1,xb-1,k-1);}
}
int T;
int main(){scanf("%d",&T);while(T--){memset(f,0,sizeof(0));memset(fa,0,sizeof(0));memset(fb,0,sizeof(0));//初始化数组 scanf("%s%s",a+1,b+1);int lena=strlen(a+1),lenb=strlen(b+1);//两个字符串长度 for(int i=1;i<=lena;i++){//计算字符串a中字母最近出现位置 for(int j=0;j<26;j++){if(a[i]==j+'a') fa[i][j]=i;else fa[i][j]=fa[i-1][j];	} }for(int i=1;i<=lenb;i++){//计算字符串b中字母最近出现位置 for(int j=0;j<26;j++){if(b[i]==j+'a') fb[i][j]=i;else fb[i][j]=fb[i-1][j];	} }for(int i=1;i<=lena;i++){//求LCS长度 for(int j=1;j<=lenb;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);}	}ans.clear();dfs(lena,lenb,f[lena][lenb]);//字符串a的长度,字符串b的长度,LCS长度 sort(ans.begin(),ans.end());//按照字典序输出,先排个序 for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;	}return 0;
} 
http://www.hskmm.com/?act=detail&tid=28240

相关文章:

  • 经营不是老板一个人的事 - 智慧园区
  • Codeforces Round 1051 (Div. 2)[A ~E]
  • 如何在 Spring Boot 应用中配置多个 Spring AI 的 LLM 客户端
  • 使用eBPF技术保护FastAPI安全
  • 项目案例作业2:对案例进行面向对象分析
  • JavaSE
  • CF2064E Mycraft Sand Sort
  • Servlet笔记
  • 第一个博客
  • k8s 主节点重启后 从节点 get 异常 - 教程
  • 多维索引技术优化数据湖查询性能
  • Umi-OCR_文字识别工具 免安装使用教程(附下载安装包)!永久免费,开源离线OCR识别软件下载
  • 【汇总】OPPO r9m 分区名、分区功能
  • 04_线程池实现
  • #D251010D. 未命名 10 (unnamed)
  • 【JAVA】从入门到放弃-01-HelloWorld - 指南
  • 离线应用程序
  • 2025表面瑕疵检测厂家TOP5推荐:表面瑕疵检测,薄膜瑕疵检测,瑕疵检测设备,瑕疵在线检测,铝箔瑕疵在线检测,外观瑕疵检测机,薄膜瑕疵检测仪,陶瓷膜瑕疵检测各种类型检测,精准高效的质量守护
  • 表格识别:不仅能识别文字,更能理解表格的结构和逻辑关系,实现输出可编辑、可分析的结构化数据
  • 同步FIFO
  • P13274 [NOI2025] 三目运算符
  • Microsoft Office不小心卸载或重装系统后,如何重新安装 ... - sherlock
  • HTTPS 抓包乱码怎么办?原因剖析、排查步骤与实战工具对策(HTTPS 抓包乱码、gzipbrotli、TLS 解密、iOS 抓包) - 实践
  • 使用JaCoCo进行代码覆盖率分析
  • 计算机视觉专家入选德国国家科学院
  • 2025 年工程管理软件/软件系统/软件App/软件平台/工程管理软件和验房系统公司/企业推荐榜:数字化转型下的实用选型指南
  • 【Java学习】【Java基础】--第1篇:入门Java和对面向对象的理解
  • solutions
  • 技术面:Spring (事务传播机制、事务失效的原因、BeanFactory和FactoryBean的关系)
  • 安装与配置MySQL 8 on Ubuntu,包括权限授予、数据库备份及远程连接