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

DCTDN2 - Dãy con tăng dài nhất (Bản TB)

Điểm: 2,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, 1 ≤ a_i ≤ 10^6~

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.

CHO AE THAM KHẢO+))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), dp;
    for (auto &i : a)
        cin >> i;
    for (int i = 0; i < n; i++)
    {
        if (dp.empty() || dp.back() < a[i])
        {
            dp.push_back(a[i]);
        }
        else
        {
            auto it = lower_bound(dp.begin(), dp.end(), a[i]);
            *it = a[i];
        }
    }
    cout << dp.size();
    return 0;
}

include <bits/stdc++.h>

using namespace std;

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

int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) {
    cin >> a[i];
}
vector<int> tail;
for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) {
        tail.push_back(x);
    } else {
        *it = x;
    }
}
cout << (int)tail.size();
return 0;

}

21

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