1 条题解

  • 0
    @ 2025-4-13 14:10:56
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200'000;
    const int MAXAI = 1'000'000'000;
    int n;
    int a[MAXN + 5];
    // f[i]: 以 b[i] 结尾的 LIS 长度
    int f[MAXN + 5];
    // g[len]: 当前长度为 len 的 LIS 的最小结尾
    int g[MAXN + 5];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
    
        int ans = 0;
        for (int i = 1; i <= n; i++)
            g[i] = MAXAI + 1;
        for (int i = 1; i <= n; i++)
        {
            int len = lower_bound(g + 1, g + n + 1, a[i]) - g;
            f[i] = len;
            g[len] = a[i];
            ans = max(ans, f[i]);
        }
        cout << ans;
    
        return 0;
    }
    
    
    • 1

    信息

    ID
    1679
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    12
    已通过
    8
    上传者