Số bước nhảy nhiều nhất thì mình nghĩ là dùng LIS là ok rồi.
Nhưng còn số cách nhảy thì phải làm sao ? Mong m.n giúp mình.
Forum VNOI đã tạm ngừng hoạt động. Các bạn có thể hỏi bài trên Group Facebook của bọn mình.
QHD + BIT giống cách làm LIS dùng BIT.
Đặt f(i) = độ dài dãy con tăng kết thúc ở i
g(i) = số dãy con tăng kết thúc ở i
Thì khi tính g(i) cần chú ý chỉ xét những cái j mà f(j) = f(i) - 1. Để làm đc cái này thì phải sort lại dãy theo f --> những phần tử có f bằng nhau ở cạnh nhau.