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

Xem PDF




Tác giả:
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\)\(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


  • 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\)\(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