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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
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
    TrungMegaLikeIT    8:12 a.m. 27 Tháng 6, 2024

    Sao bản dễ 1400 điểm mà bản khó có 400 điểm thôi z?

    2 phản hồi

    • -3
      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;
      }


      • 6
        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


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

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


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

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


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

              FENWICCK vẫn có thể


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

                tle 4 test khó hiểu

                2 phản hồi

                • 6
                  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