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

2 ACwing 272 LCIS 最长公共上升子序列 题解

ACwing 272 LCIS 最长公共上升子序列

题面

对于两个数列 A 和 B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列

给定序列 \(A\)\(B\) ,求 \(A\)\(B\) 的最长公共上升子序列

\(|A,B| \le 3000\)

题解

\(f(i,j)\) 表示 \(A_1...A_i\)\(B_1...B_j\) \(B_j\) 为结尾的 LCIS ,可以分两种情况转移

  • \(A_i \not= B_j\)\(f(i,j) = f(i - 1, j)\)
  • \(A_i = B_j\)\(f(i,j) = \max_{k < j,B_k < B_j} \{f(i - 1, k)\} + 1\)

转移的候选状态集合是只增不减的,所以可以用一个变量维护,转移时间复杂度降为 \(O(1)\) 总时间复杂度为 \(O(n^2)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 3e3 + 10;int n;
int a[N], b[N];
int f[N][N];int main () {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) cin >> b[i];for (int i = 1; i <= n; i++) {int val = 0;for (int j = 1; j <= n; j++) {if (a[i] == b[j]) {f[i][j] = val + 1;} else {f[i][j] = f[i - 1][j];}if (b[j] < a[i]) val = max (val, f[i - 1][j]);}}int ans = 0;for (int i = 1; i <= n; i++) {ans = max (ans, f[n][i]);}cout << ans << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=25016

相关文章:

  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025