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

Points: 0.05 (partial)

Time limit: 0.3s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

Bài cổ điển

Problem types

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

(Giống bài LIQ) Cho một dãy gồm ~N~ số nguyên (~1~ ~\leq~ ~N~ ~\leq~ ~30000~). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

Dòng đầu tiên gồm số nguyên ~N~.
Dòng thứ hai gồm ~N~ số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Sample Input

5
2 1 4 3 5

Sample Output

Comments

Please read the guidelines before commenting.

-5

vuongbankien012 commented on Sept. 3, 2024, 5:48 a.m.

ai vote up tui tui tang Yuki Suo ngoai doi cho

This comment is hidden due to too much negative feedback. Show it anyway.

-7

nongquan commented on July 11, 2024, 4:13 a.m. ← edited →

Ý tưởng : lấy từ anh yugihacker thuật toán : tham lam + tknp độ phức tạp : O(n.logn) mình sẽ tạo thêm mang f với f[i]: phần tử cuối nhỏ nhất của dãy con độ dài i khi đó độ dài mảng f là kq bài toán ta tham lam ở chỗ có nhiều dãy con độ dài i nhưng ta sẽ lấy dãy có ptu kết thúc nhỏ nhất để tối ưu bài toán khi chọn thêm phần tử để thêm vào dãy đó ta thấy mảng f là mảng tăng dần để chứng minh nó đúng ta sẽ chứng minh ngược lại của nó là sai Ví dụ : f[1] = 3 và f[2] = 2 mà theo quy tắc tham lam ở trên thì dãy con độ dài 1 kia phải lấy ptu gtri là 2 để tối ưu chứ k lưu giá trị 3 như ví dụ và ta có thể thêm ptu gtri 3 kia vào dãy con độ dài 2 kia để tạo thành dãy con có độ dài là 3 kết thúc là 3 vì mảng f tăng dần nên ta được phép tknp trong mảng f Duyệt từng phần tử mảng a rồi tknp phần tử có giá trị lớn hơn hoặc bằng a[i] gọi k là vị trí ptu đó trong mảng f thì ta có thể thêm ptu a[i] vào dãy con độ dài k-1 vì ptu kết thúc của dãy độ dài k-1 nhỏ hơn a[i] khi đó nó tạo thành dãy con độ dài k ptu kết thúc là a[i]

include<bits/stdc++.h>

define ll long long

using namespace std; ll n, a[100003], f[100003], maxn = 1;

int main() { cin>>n; for (int i = 1; i <= n; i++) { cin>>a[i]; } f[1] = a[1]; for (int i = 2; i <= n; i++) { ll k = lower_bound(f+1, f+maxn+1, a[i])-f; f[k] = a[i]; maxn = max(maxn, k); } cout<<maxn; }

This comment is hidden due to too much negative feedback. Show it anyway.

-8

This comment is hidden due to too much negative feedback. Show it anyway.

-3

trongnghia commented on June 12, 2024, 11:23 a.m.

bài này khó thiệt nha =))

-3

nhanphamj commented on June 8, 2024, 7:52 a.m.

đơn giản

2

lenguyenminhkhang2b commented on April 22, 2024, 1:54 p.m.

Mọi người cho mình hỏi là bài này có bản in ra dãy con không do mình học thấy có bài nhx ko có test nên mình hỏi. Mong mọi người giúp đỡ ạ. Cảm ơn mọi người nhiều ! =)) Đừng down vote mình nha

1

Le_peace commented on April 25, 2024, 6:54 a.m.

khong ban nhe

-5

thaihong7577 commented on April 22, 2024, 5:25 a.m.

Spoil!

This comment is hidden due to too much negative feedback. Show it anyway.

14

YugiHackerKhongCopCode commented on March 21, 2024, 4:47 p.m.

Spoil!

Cách 1: Quy hoạch động + Tìm kiếm nhị phân

Gọi mảng ~b~ : ~b_i~ là giá trị nhỏ nhất của phần tử cuối trong tất cả các dãy con tăng độ dài ~i~

Mảng ~b~ là một dãy không giảm (~b_i \le b_{i+1}~ với mọi ~i~)

Để tìm độ dài dãy con tăng dài nhất kết thúc tại vị trí ~a_i~, ta tìm ra vị trí ~j~ lớn nhất thoả mãn ~b_j \le a_i~, như vậy ta có thể tạo ra một dãy con tăng độ dài ~j+1~

Do mảng ~b~ không giảm, dễ dàng tìm kiếm được vị trí ~j~ lớn nhất bằng tìm kiếm nhị phân

Độ phức tạp ~O(n \cdot logn)~

Link video solution: Dãy Con Tăng Dài Nhất sử dụng Tìm Kiếm Nhị Phân

Cách 2: Quy hoạch động + Segment tree hoặc Fenwick Tree (update sau)

0

nguyenthiennhan17 commented on June 20, 2024, 9:27 a.m.

Không có th bi = bi + 1 anh ạ

-31

vendettas commented on Feb. 17, 2024, 6:07 a.m.

khi bạn deo nhắn gì sai nhưng vẫn bị downvote <(")

This comment is hidden due to too much negative feedback. Show it anyway.

-23

KiraYoshikage commented on Feb. 2, 2024, 3:33 p.m.

ai hỏi?

This comment is hidden due to too much negative feedback. Show it anyway.

22

triclone_3 commented on Nov. 8, 2023, 4:15 a.m. ← edit 3 →

Các bạn xem thì ủng hộ mình 1 down vote, mình cảm ơn! Bài này thì các bạn nên sử dụng multiset để các phần tử giống nhau sẽ không bị xoá.

Đầ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

-30

huynhquocluatit10 commented on Oct. 15, 2023, 12:46 p.m.

Thanh Phong deptrai nhat the gioi

This comment is hidden due to too much negative feedback. Show it anyway.

-55

giataino commented on Oct. 14, 2023, 9:26 a.m.

d!t me bai nhon lu

This comment is hidden due to too much negative feedback. Show it anyway.

-38

nhan19042007 commented on Oct. 12, 2023, 6:53 a.m. ← edited →

bài này mình lỡ cmt mà ko biết xóa cmt sao xin mn đừng downvote em ạ :((

This comment is hidden due to too much negative feedback. Show it anyway.

-88

nthquan_1505 commented on March 30, 2023, 4:22 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-40

maintainit commented on Feb. 21, 2023, 2:17 p.m.

mik ga vl nghi deo ra

This comment is hidden due to too much negative feedback. Show it anyway.

-17

harmxvu commented on June 24, 2023, 1:15 p.m.

dùng quy hoạch động bạn

This comment is hidden due to too much negative feedback. Show it anyway.

-32

boneman23 commented on Jan. 8, 2023, 9:47 a.m.

hình như giống bản dễ nhỉ?

This comment is hidden due to too much negative feedback. Show it anyway.

-22

MaiThanh1342 commented on Jan. 9, 2023, 8:54 a.m.

quan trong la thoi gian thuc thi thoi

This comment is hidden due to too much negative feedback. Show it anyway.

-32

lkva2019 commented on Jan. 7, 2023, 9:00 a.m.

kho qua ae :o

This comment is hidden due to too much negative feedback. Show it anyway.

-11

maintainit commented on Feb. 21, 2023, 2:19 p.m.

uk

This comment is hidden due to too much negative feedback. Show it anyway.

-18

thanh20092007 commented on Aug. 28, 2022, 3:31 a.m.

kho the nho

This comment is hidden due to too much negative feedback. Show it anyway.

15

minhducle31o commented on April 19, 2023, 9:09 a.m.

bạn cố gắng là làm được mà. cố lên!!!

-5

codelozd commented on Feb. 9, 2024, 8:37 a.m.

oke ban

This comment is hidden due to too much negative feedback. Show it anyway.

-136

modwwe commented on July 11, 2022, 5:18 p.m.

bài dễ vl

This comment is hidden due to too much negative feedback. Show it anyway.

-14

minhducle31o commented on April 19, 2023, 9:09 a.m.

bạn nên xem lại ngôn ngữ của mình

This comment is hidden due to too much negative feedback. Show it anyway.

-5

codelozd commented on Feb. 9, 2024, 8:39 a.m.

oke ban

This comment is hidden due to too much negative feedback. Show it anyway.

23

kennikai commented on Dec. 31, 2021, 5:04 a.m. ← edit 2 →

bài này làm thấm phết!