柿子饼同学 发表于 2024-6-30 17:06:48

[心之碎片][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;
}


FishC 发表于 2024-6-30 17:07:03

鱼油呀,这道题可真是个小妖精,让我给你解剖一下吧。首先,咱们搞清楚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]
查看完整版本: [心之碎片][0630] - LCIS