Mọi người cho em hỏi cách làm bài NTSEQ (http://vn.spoj.com/problems/NTSEQ/). Em cảm ơn!
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.
Huyền anh hỏi hả :v
Không. Tự hỏi thôi
Đầu tiên em lập công thức QHD để tìm dãy con tăng dài nhất kết thúc tại i và số lượng dãy con tăng tương ứng. Sau đó em tăng tốc bằng cách dùng CTDL.
Vâng, anh nói luôn công thức QHĐ tính số lượng dãy con tăng tương ứng được không ạ? Em cảm ơn
F[I] là là độ dài dãy con tăng dài nhất kết thúc ở vị trí i
G[i] là số dãy con tăng có độ dài là fi] kết thúc ở vị trí i
G[i] = Sum(g[j]) với mọi j < i, a[j] < a[i], f[j] = f[i] - 1
Sau đó tối ưu bằng BIT hoặc IT