LIS：最长上升子序列

dongzirui0817 · 2025-10-26 12:29:26 · 算法·理论

LIS，即最长上升子序列。相信你们都会 O(n^2) 了，这里不讲了。这里讲 O(n\log n)。

LIS 例题

注意下面的做法是严格上升。

我们来考虑一个状态 f_i，表示长度为 i 的最长上升子序列的最后一项最小为多少。

显然越小答案越优，所以这是没问题的。我们考虑现在的最长上升子序列长为 m。现在考虑 A_k。那么：

• 如果 f_m<A_k，那么 f_{m+1} \gets A_k，然后 m \gets m + 1。
• 如果 f_m\ge A_k，那么我们找到最小的满足 f_j\ge A_k 的位置，则：
  • 所以我们就二分找到这个 j，然后 f_j \gets A_k 即可。

使用 lower_bound 可更简洁地找到这个 j。

int n, cnt = 0;
int c[100010];

int main() {
    scanf("%d", &n);
    for (int i = 1, x ; i <= n ; i++) {
        scanf("%d", &x);
        if (x > c[cnt]) c[++cnt] = x;
        else c[lower_bound(c + 1, c + cnt + 1, x) - c] = x;
    }
    printf("%d\n", cnt);
    return 0;
}

现在，我们把它运用在题目当中。

递增

贪心。显然挑出一个 LIS，把剩下的修改就一定可以满足。证明：无需证明。

所以答案就是 n 减最长上升子序列的长度。

金币收集

由于从左往右走，所以考虑按地点排序。直接考虑有点困难，但注意到小 A 站原地越久越容易丢失越多的金币，所以考虑设 p_i 为小 A 到 i 号金币处前，最多在其他地方不动多久。那么如果原地不动时间超过 p_i，就领不到了。

显然 p_i = t_i - x_i。那么发现一个很重要的结论：答案就是以 0 为首项的 p 的最长不降子序列！

该结论不必多说，只是不好发现。

注意：

• 求最长不降子序列时，要用的是 upper_bound。证明可以像 LIS 来证。
• 注意 p_i<0 的情况。

int n;
pair <int, int> c[100010];
int f[100010], cnt = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i++)
        scanf("%d%d", &c[i].first, &c[i].second);
    sort(c + 1, c + n + 1);
    for (int i = 1 ; i <= n ; i++) {
        int x = c[i].second - c[i].first;
        if (x < 0) continue;
        if (f[cnt] <= x)
            f[++cnt] = x;
        else f[upper_bound(f + 1, f + cnt + 1, x) - f] = x;
    }
    printf("%d\n", cnt);
    return 0;
}

希望本文章对你们有所帮助。