Dãy con tăng dài nhất (Bản khó) - LCOJ: Luyện Code Online Judge

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

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Input

Dòng đầu chứa số nguyên dương ~N~;
Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

~1 ≤ n ≤ 10^5, |a_i| ≤ 10^9~.

Output

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

Sample

Input #1

6
1 2 5 4 6 2

Output #1

Hint

Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

0

TP25_B044 đã bình luận lúc 27, Tháng 2, 2026, 15:55 ← chỉnh sửa →

Cách giải bằng Fenwick Tree

Heading 4

! Từ tính chất của dãy con đơn điệu tăng, ta có thuật toán như sau: ! Thử xét một phần tử a[i], ta đếm xem có bao nhiêu phần tử nhỏ hơn a[i] nằm trong đoạn [1, i-1] có độ dài là d[i], khi đó độ dài lớn nhất tại vị trí i của dãy là (d[i] + 1). ! Sau đó ta thực hiện việc cập nhật độ dài lớn nhất cho các phần tử >= a[i]. ! Kết quả cuối cùng của bài toán sẽ là độ dài lớn nhất tìm được của cây. ! Bởi vì giá trị của a lớn, vì vậy ta cần phải nén tọa độ. * Code: *
! >! #include <iostream> ! >! #include <vector> ! >! #include <algorithm> ! >! using namespace std; ! >! ! >! struct Fenwick{ ! >! int n; ! >! vector<int> bit; ! >! Fenwick(int n) : n(n), bit(n + 1, 0) {} ! >! void update(int x, int v){ ! >! for(; x <= n; x += x & -x) bit[x] = max(bit[x], v); ! >! } ! >! int getRes(int x){ ! >! int len = 0; ! >! for(; x > 0; x -= x & -x) len = max(len, bit[x]); ! >! return len; ! >! } ! >! }; ! >! ! >! int getId(const vector<int> &b, int x){ ! >! return int(lowerbound(b.begin(), b.end(), x) - b.begin()) + 1; ! >! } ! >! ! >! int main(){ ! >! iosbase::syncwithstdio(false); ! >! cin.tie(NULL); ! >! int n; ! >! cin >> n; ! >! vector<int> a(n), b; ! >! for(int i = 0; i < n; ++i) cin >> a[i], b.push_back(a[i]); ! >! sort(b.begin(), b.end()); ! >! b.erase(unique(b.begin(), b.end()), b.end()); ! >! Fenwick fk(b.size()); ! >! int len = 0; ! >! for(int i = 0; i < n; ++i){ ! >! int x = getId(b, a[i]); ! >! int best = fk.getRes(x - 1); ! >! int cur = best + 1; ! >! len = max(len, cur); ! >! fk.update(x, cur); ! >! } ! >! cout << len; ! >! return 0; ! >! } ! Độ phức tạp thuật toán: O(n log n).

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int N;
cin >> N;
vector&lt;long long> a(N);
for (int i = 0; i < N; i++) {
    cin >> a[i];
}

vector&lt;long long> tail; // tail[i] = min last element of length i+1 LIS
for (auto x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x);
    else *it = x;
}

cout << tail.size() << "\n";
return 0;

}

0

dainghiajustiin đã bình luận lúc 8, Tháng 6, 2025, 17:07

*LỜI GIẢI DÙNG BIT, MERGE SORT VÀ NÉN SỐ BẰNG PYTHON, LƯU Ý CODE CHÍ MANG TÍNH CHẤT THAM KHẢO: *

https://ideone.com/lCyzOp

-1

buiminhkhoi đã bình luận lúc 9, Tháng 2, 2025, 16:22

anh Dat cua em dep trai quaaaaaaaaaaaaaaa

-1

votunganh đã bình luận lúc 17, Tháng 5, 2024, 12:24

Cho em xin code C++ đi ạ!

19

tri_88 đã bình luận lúc 8, Tháng 1, 2024, 8:26 ← chỉnh sửa →

Đầu tiên nhập vào một số n.

Khi nào n > 0.

Thì nhập vào 1 số a.

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 a

Sau khi dùng hàm lower_bound() xong các bạn phải cộng thêm 1 vì vị trí m trong multiset thực tế là m+1.

Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi.

(Nếu như m != multiset.end() thì xoá đi để tìm 1 vị trí khác thoả mãn)

Thì kích thước của multiset sẽ là kết quả của bài.

Code mẫu (C++) tại Đây

1

Very_skibidi đã bình luận lúc 2, Tháng 11, 2024, 8:42

Giải thích cho ai dùng python là lowerbound giống bisect.bisectleft (xem ở đây) Multiset giống list (mảng) Cho bạn nào lười sử dụng bisect thì dùng tìm kiếm nhị phân ( Đây )

1

sang41dz đã bình luận lúc 10, Tháng 3, 2024, 10:56

tại sao bạn dùng multiset thay vì vector nhỉ

2

_SUGAR_BADBOY_ đã bình luận lúc 31, Tháng 10, 2023, 15:08

cop code mà