最佳彩色带
2022/8/22 23:22:56
本文主要是介绍最佳彩色带,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://www.acwing.com/problem/content/1531/
思路:
最长公共子序列模型,唯一不同的一点是:他一个i可以选择多个j。
P:2 3 1 5 6
S:2 2 4 1 5 5 6 3 1 1 5 6
f[i][j]:
状态表示:
集合:在p[1,i]中出现且在s[1,j]中出现的公共子序列的集合
属性:长度的最大值
状态计算:
分类:
(1)公共子序列不含p[i]和s[j]-->f[i-1][j-1]
(2)公共子序列含p[i],不含s[j]-->包含在f[i][j-1]中
(3)公共子序列不含p[i],含s[j]-->包含在f[i-1][j]中
(4)公共子序列含p[i],s[j]-->f[i][j-1]+1
所以:
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(p[i]==s[j]) f[i][j]=max(f[i][j],f[i][j-1]+1)
Notes1:
(2)包含的原因是:f[i][j-1]是指在p[1,i]中和s[1,j-1]中出现的公共子序列
但是没说公共子序列一定包含p[i],公共子序列可以包含p[i]也可以不包含
所以含p[i]的情况只是f[i][j-1]的一个子集
(3)同理
Notes2:
(4)f[i][j-1]的原因是p中的一个数字可以对应S中相同的好多数字
Notes3:
最终式子中不含情况(1)的原因是它已经被包含在f[i][j-1]和f[i-1][j]之中了
#include <iostream> using namespace std; const int N = 210, M = 10010; int n, m, l; int p[N], s[M]; int f[N][M]; int main() { cin >> n; cin >> m; for (int i = 1; i <= m; i ++ ) cin >> p[i]; cin >> l; for (int i = 1; i <= l; i ++ ) cin >> s[i]; for (int i = 1; i <= m; i ++ ) for (int j = 1; j <= l; j ++ ) { f[i][j] = max(f[i - 1][j], f[i][j - 1]); if (p[i] == s[j]) f[i][j] = max(f[i][j], f[i][j - 1] + 1); } cout << f[m][l] << endl; return 0; }
这篇关于最佳彩色带的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?