Dãy con tăng dài nhất (bản khó)

Xem PDF
Tác giả:
corona
Dạng bài
Điểm: 400 (p) Thời gian: 0.2s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
  • Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

  • Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Example

Test 1

Input 
6
1 2 5 4 6 2
Output 
4

Bình luận


  • 0
    hjhjhjhjhj    7:35 a.m. 6 Tháng 4, 2024

    include <bits/stdc++.h>

    using namespace std;
    int main(){
    multiset <int> mulse;
    int n, a, m;
    cin>>n;
    for(int i = 1; i <= n; i++) {
    cin>>a;
    mulse.insert(a);
    auto m=mulse.lower_bound(a);
    m++;
    if (m!=mulse.end())
    mulse.erase(m);
    }
    cout<<mulse.size();
    return 0;
    }


    • 4
      Kairi    8:48 a.m. 30 Tháng 12, 2023

      Các bạn sẽ không thấy mình AC ở phần danh sách bài nộp đâu vì mình ko thích làm, mình là owner của nick VNOJ này
      Đầu tiên nhập vào một số n.
      Sau đó nhập n số vào cho hết chúng vào multiset.
      Tiếp theo dùng hàm lower_bound() để tìm m là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng với giá trị chỉ định.
      Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi. Code mẫu (C++) tại đây


      • -3
        penistone    10:13 p.m. 28 Tháng 9, 2023

        bài qhđ còn nhiều người làm đc hơn so với mấy bài lớp 6, thế này thì editorial hơi lợi quá


        • 4
          scratch_huykhanh    12:31 a.m. 13 Tháng 4, 2023

          Bản dễ: 1400p
          Bản khó: 400p
          perfect


          • 1
            minhtuanitk20    3:12 p.m. 27 Tháng 10, 2021

            FENWICCK vẫn có thể


            • -1
              minhtuanitk20    3:09 p.m. 27 Tháng 10, 2021

              tle 4 test khó hiểu

              1 phản hồi

              • 5
                cuom1999    1:43 a.m. 15 Tháng 7, 2020

                Đã update test (credit: A519LeVanDuc)


                • 5
                  SPyofgame    5:09 a.m. 14 Tháng 6, 2020 ← chỉnh sửa 7

                  Spoiler Alert

                  Hint 1

                  • Thử từng dãy con một

                  Kiểm tra xem nếu nó là dãy con tăng dần

                  Xuất dãy có độ dài dài max

                  Hint 2

                  • Gọi mảng \(f[]\) với \(f_i\) là giá trị độ dài tối đa tính tới \(i\) || init \(f_i = 1\)

                  Ta duyệt \(\forall j < i\) tìm vị trí \(j\) thỏa \(a_j < a_i\)

                  Ta liên tục chọn các vị trí \(j\) có \(f_j\) lớn nhất

                  \(result = max(x \in f)\)

                  Hint 3

                  • Gọi mảng \(b[]\) với \(b_i\) là giá trị nhỏ nhất trong các dãy tăng có độ dài \(i\) || init \(b_i = +oo\)

                  Gọi res là giá trị \(max(f_j\) \(|\) \(j \leq i)\) hay độ dài max trong các dãy tăng

                  \(\forall i \leq n\), ta chặt nhị phân \(f_i\) = vị trí cận dưới của \(a_i\) trên mảng \(b_{[0, res]}\)

                  Sau đó gán \(b_{f_i} = a_i\) là xong

                  \(result = max(x \in f) + 1 - p\) với p là số thứ tự vị trí bắt đầu mảng \(b\)

                  Hint 4

                  • Nếu các bạn muốn lấy mảng LIS

                  Gọi mảng \(LIS[]\) là mảng cần tìm

                  Duyệt ngược từ vị trí cuối về, nếu \(f_i = res\) thì thêm phần tử vào cuối mảng \(LIS\) rồi giảm res

                  Đảo ngược lại mảng \(LIS[]\) sau quá trình trên ta thu được dãy con dài nhất

                  Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(n)\) auxiliary space | LIS-problem, DP, Binary_search

                  C++
                  int lis(const vector<int> a)
{
    int n = a.size();
    vector<int> f(n, 1), b(n, +INF);

    int res = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin();
        maximize(res, f[i]);
        b[f[i]] = a[i];          
    }
    return res + 1;

    /// lay mang LIS
    vector<int> LIS;
    while (n--)
        if (f[n] == res)
            LIS.push_back(a[n]), res--;

    reverse(all(LIS));
    return LIS.size();
}

                  Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(n)\) auxiliary space | Online Solving, LIS-problem, DP, Binary_search
                  C++
                  int main()
{
    int n = readInt();
    vector<int> a, f, b;

    int res = 0;
    for (int i = 0; i < n; ++i) {
        a.push_back(readInt());
        b.push_back(+INF);
        f.push_back(lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin());
        maximize(res, f[i]);
        b[f[i]] = a[i];
    }

    cout << res + 1;
    return 0;
}

                  1 phản hồi