[心之碎片][0630] - LCIS
本帖最后由 柿子饼同学 于 2024-6-30 17:16 编辑AcWing.272
提交 5 次
用时 2 h
知识点
线性dp
思路
设 f(i, j) 是 A前 i 个, B前 j 个数, 且以 Bj 结尾的 LCIS
Ai == Bj 时, ans = f(i - 1, k) + 1, 且满足 Bk < Bj = Ai, 0 < k < j
不等于时, ans = f(i - 1, j)
优化:
发现决策集合只增加, 每次 j 的循环中 i 是固定的, 即 Bk < Ai 的条件是固定下来的
所以遇到 Bj < Ai 时就用 temp = max(temp, f(i - 1, j)) 更新决策集合
另一种视角: 相等时只能从 Bk < Bj 转移过来
f 数组可以压成 1 维, f(j) 代表以 Bj 结尾的和 A 的 LCIS
Ai == Bj 时, f(j) = max(f(j), maxv + 1)
小于时, 因为没有被更新到, 所以 f(j) 相当于 i - 1 阶段的 f(j)
需要进步
优化的时候知道是只增, 但是没写出来, 没有钉死 Ai 是固定的才导致写不了
在看次层循环时, 考虑优化的时候不用关心阶段(只是利用那个 j 的循环而已), 只需要保证现在选择的状态没被更新即可
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n, A, B, f;
int ans, mx;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> A;
for(int i = 1; i <= n; i++) cin >> B;
for(int i = 1; i <= n; i++){
int maxv = 0;
for(int j = 1; j <= n; j++){
if(A == B) f = max(f, maxv + 1);
if(A > B) maxv = max(maxv, f);
}
}
for(int i = 1; i <= n; i++) ans = max(ans, f);
cout << ans;
return 0;
}
鱼油呀，这道题可真是个小妖精，让我给你解剖一下吧。首先，咱们搞清楚LCIS是啥：**Longest Common Increasing Subsequence，最长公共上升子序列**。这名字一听就很吓人对吧？但是不用担心，我来带你一步步搞定它！
咱们先简单点，把这段思路和代码拆开讲。
## 思路
我们用动态规划（DP）来解决这个问题。设`f(i, j)`表示数组`A`前`i`个元素和数组`B`前`j`个元素，并且以`B`结尾的LCIS长度。
### 转移方程
1. **当`A == B`时**：
这时候，我们可以从`B`中所有小于`B`的序列中选择一个最长的，再加上现在的这个元素：
\[
f(i, j) = \max(f(i-1, k)) + 1 \quad \text{其中} \quad (0 < k < j \text{且} B < B)
\]
2. **当`A != B`时**：
这时候就没什么好比的了，直接保持上一个状态即可：
\[
f(i, j) = f(i-1, j)
\]
### 优化
我们发现，对于每个`j`，在`i`固定的时候，`Bk < Ai`的条件是固定的，所以我们大可以在一次循环里搞定这部分信息。
因此，我们只需要一个额外的变量`maxv`来记录`f(i-1, k)`中的最大值，这样就不用再嵌套循环找`k`了。
### 压缩维度
由于我们每次只需要上一行的状态，可以直接把二维数组`f`压缩成一维。
## 代码实现
下面就是优化后的代码：
#include <iostream>
#include <vector>
using namespace std;
const int N = 3005;
int n, A, B, f;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// 输入A和B的长度
cin >> n;
// 输入数组A
for(int i = 1; i <= n; i++) cin >> A;
// 输入数组B
for(int i = 1; i <= n; i++) cin >> B;
int ans = 0;
// 遍历A中的每一个元素
for(int i = 1; i <= n; i++) {
int maxv = 0;// 记录当前的最大LCIS
for(int j = 1; j <= n; j++) {
if(A == B) f = max(f, maxv + 1);
if(B < A) maxv = max(maxv, f);
ans = max(ans, f);
}
}
cout << ans << endl;
return 0;
}
唉，你看，这不就搞定了么？要记住，动态规划讲究的是**状态转移**，通过记录和更新状态，我们就能一步步找到最优解。希望这个解释让你脑洞大开，解决LCIS这道难题不再抓耳挠腮啦！继续加油哦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]