51Nod 1006 最长公共子序列Lcs
2021/7/26 6:07:19
本文主要是介绍51Nod 1006 最长公共子序列Lcs,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:51Nod 1006 最长公共子序列Lcs
题目大意:
题解:
最长公共子序列模板题,设\(dp[i][j]\)为字符串\(A[1...i]\)与字符串\(B[1...j]\)的最长公共子序列长度,则状态转移方程为:
用\(pre\)数组记录上一个状态,通过递归输出最长公共子序列。
#include <iostream> #include <string> using namespace std; int dp[1010][1010], pre[1010][1010]; string a, b; void print(int i, int j) { if (!i || !j) { return; } if (pre[i][j] == 0) { print(i - 1, j - 1); cout << a[i]; } else if (pre[i][j] == 1) { print(i - 1, j); } else { print(i, j - 1); } } int main() { cin >> a >> b; int lena = a.length(), lenb = b.length(); a = ' ' + a; b = ' ' + b; for (int i = 1; i <= lena; ++i) { for (int j = 1; j <= lenb; ++j) { if (a[i] == b[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; pre[i][j] = 0; } else { if (dp[i - 1][j] >= dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; pre[i][j] = 1; } else { dp[i][j] = dp[i][j - 1]; pre[i][j] = 2; } } } } print(lena, lenb); return 0; }
这篇关于51Nod 1006 最长公共子序列Lcs的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解