DCTDN3 - Dãy con tăng dài nhất (Bản khó)
Xem dạng PDF
Gửi bài giải
Điểm:
3,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, 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
4
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
Đầu tiên nhập vào một số
n.Khi nào
n > 0.Thì nhập vào
1sốa.Tiếp theo dùng hàm
lower_bound()để tìmmlà vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng vớiaSau khi dùng hàm
lower_bound()xong các bạn phải cộng thêm1vì vị trímtrong 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ìm1vị 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
tại sao bạn dùng multiset thay vì vector nhỉ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
dp ez
cop code mà
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
eheheh
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.