Đếm số cách tạo ra dãy con tăng dài nhất

Chào mọi người ạh, cho em hỏi làm sao để mình đếm được số cách tạo ra dãy con tăng

rogp10 viết 12:22 ngày 01/10/2018

Dãy liên tục dễ hơn (rất dễ luôn) không liên tục

Tin Tin viết 12:22 ngày 01/10/2018

pùn một cái là dãy này không liên tục mới ghê :v

HK boy viết 12:31 ngày 01/10/2018

Dãy liên tục dễ hơn (rất dễ luôn) không liên tục

Quy hoạch động đó :v
Mà bạn đã hỏi câu này trên VNOI Group mà vẫn chưa tìm được câu trả lời xác đáng sao :v

Tin Tin viết 12:34 ngày 01/10/2018

Éc… cái đó ko ổn pạn ạh. Nếu làm cách đó thì y chang cách mình 10% test

HK boy viết 12:34 ngày 01/10/2018

f[i] là số dãy con tăng có phần tử cuối là a[i]
-> với mọi i < j, a[i] < a[j] thì f[j] = sigma(f[i])
-> Độ phức tạp O(n^2)

Cải tiến thì dùng BIT -> xuống O(n log n)

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Tin Tin

0 chủ đề

0 bài viết

Tác giả nổi bật

Từ khóa nổi bật

Chủ đề nổi bật