Loading... # 题目描述 熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。 小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。 小沐沐说，对于两个数列$A$和$B$，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。 奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。 不过，只要告诉奶牛它的长度就可以了。 数列$A$和$B$的长度均不超过$3000$ # 输入格式 第一行包含一个整数$N$，表示数列$A$，$B$的长度。 第二行包含$N$个整数，表示数列$A$。 第三行包含$N$个整数，表示数列$B$。 # 输出格式 输出一个整数，表示最长公共上升子序列的长度。 # 解题思路 先分别考虑最长公共子序列和最长上升子序列的状态表示： - 最长公共子序列：`dp[i][j]`表示`A`的前i个元素的子序列和`B`的前j个元素的子序列的最长公共子序列 - 最长上升子序列：`dp[i]`表示`A`的前i个元素的子序列中单调递增的子序列的最大长度 - 最长公共上升子序列：综合考虑以上两个状态表示的定义， 最长公共上升子序列的状态如下： - 状态表示： - 集合：`dp[i][j]`表示`A`的前i个元素的子序列和`B`的前j个元素的子序列的公共上升子序列， 其中必须以`B[j]`结尾 - 属性：所有公共上升子序列中包含的元素数目的最大值 - 状态计算 - 由不包括`A[i]`的公共上升子序列转移得到 - `dp[i][j]=max(dp[i][j], dp[i - 1][j])` - 由包括`A[i]`的公共上升子序列转移得到 - 需要满足`A[i] == B[j]` - 需要满足`k < j && B[j] > B[k]` - `dp[i][j] = max(dp[i - 1][k] + 1, dp[i][j])` # AC代码 朴素的写法需要三重循环 ```cpp for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) { dp[i][j] = dp[i - 1][j]; if (A[i] == B[j]) { dp[i][j] = max(dp[i][j], 1); for (int k = 1; k < j; k ++ ) if (B[j] > B[k]) dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1); } } } ``` 注意到： - 当且仅当`A[i] == B[j]`才会进入第三层循环 - 当且仅当`B[j] > B[k]`即`A[i] > B[k]`才会更新`dp[i][j]`到所有`k < j && dp[i - 1][k]`的最大值 - 因此可以在遍历第二重循环`j`并且当存在`B[j] < A[i]`动态更新`mx = max(mx, dp[i - 1][j] + 1)` - `mx`的初值应该是1(子序列仅包括`A[i]`和`B[j]`) 优化后的代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 1e3 + 10; int n; int A[N], B[N]; int dp[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 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 mx = 1; for(int j = 1; j <= n; j ++) { dp[i][j] = dp[i - 1][j]; if(A[i] == B[j]) dp[i][j] = max(dp[i][j], mx); if(B[j] < A[i]) mx = max(mx, dp[i - 1][j] + 1); } } int res = 0; for(int i = 1; i <= n; i ++) res = max(res, dp[n][i]); cout << res << endl; return 0; } ``` 最后修改：2025 年 01 月 16 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏