[心之碎片][0630] - LCIS

柿子饼同学

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[N], B[N], f[N];
int ans, mx;

int main(){
    ios::sync_with_stdio(0);
    cin.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 maxv = 0;
        for(int j = 1; j <= n; j++){
            if(A[i] == B[j]) f[j] = max(f[j], maxv + 1);
            if(A[i] > B[j]) maxv = max(maxv, f[j]);
        }
    }

    for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout << ans;

    return 0;
}

FishC

鱼油呀，这道题可真是个小妖精，让我给你解剖一下吧。首先，咱们搞清楚LCIS是啥：**Longest Common Increasing Subsequence，最长公共上升子序列**。这名字一听就很吓人对吧？但是不用担心，我来带你一步步搞定它！

咱们先简单点，把这段思路和代码拆开讲。

## 思路
我们用动态规划（DP）来解决这个问题。设`f(i, j)`表示数组`A`前`i`个元素和数组`B`前`j`个元素，并且以`B[j]`结尾的LCIS长度。

### 转移方程
1. **当`A[i] == B[j]`时**：
   这时候，我们可以从`B`中所有小于`B[j]`的序列中选择一个最长的，再加上现在的这个元素：
   \[
   f(i, j) = \max(f(i-1, k)) + 1 \quad \text{其中} \quad (0 < k < j \text{且} B[k] < B[j])
   \]
2. **当`A[i] != B[j]`时**：
   这时候就没什么好比的了，直接保持上一个状态即可：
   \[
   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[N], B[N], f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 输入A和B的长度
    cin >> n;
    // 输入数组A
    for(int i = 1; i <= n; i++) cin >> A[i];
    // 输入数组B
    for(int i = 1; i <= n; i++) cin >> B[i];

    int ans = 0;

    // 遍历A中的每一个元素
    for(int i = 1; i <= n; i++) {
        int maxv = 0;  // 记录当前的最大LCIS
        for(int j = 1; j <= n; j++) {
            if(A[i] == B[j]) f[j] = max(f[j], maxv + 1);
            if(B[j] < A[i]) maxv = max(maxv, f[j]);
            ans = max(ans, f[j]);
        }
    }

    cout << ans << endl;
    return 0;
}

唉，你看，这不就搞定了么？要记住，动态规划讲究的是**状态转移**，通过记录和更新状态，我们就能一步步找到最优解。希望这个解释让你脑洞大开，解决LCIS这道难题不再抓耳挠腮啦！继续加油哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。