cho mình xin thuật toán bài này với. chặt nhị phân á?
cho mình xin thuật toán bài này với. chặt nhị phân á?
Bạn nên nói rõ là tại sao bạn lại nghĩ là chặt nhị phân ? và chặt nhị phân như thế nào ? Anw, bài này gợi ý là dùng QHD nha bạn.
Thuật toán bài này tương tự như bài LIS, F(i) = dãy con tăng dài nhất kết thúc ở A[i].
Chú ý là để làm tốt hơn O(N^2) <cụ thể là O(NlogN)> thì ta sử dụng thêm một mảng minA[] với minA[i] = A[j] nhỏ nhất mà F(j) = i, nhờ đó việc tính giá trị của F(i) với mỗi i có thể thực hiện trong O(logN) bằng việc chặt nhị phân trên mảng minA[].
Sau khi tính xong mảng F[], ta quét lại dãy A[] một lần nữa, lần này để đếm số dãy con, khi đó minA[i] không chỉ lưu A[j] nhỏ nhất nữa, mà lưu tất cả các A[j] mà F(j) = i theo thứ tự không tăng, nhờ đó ta có thể chặt nhị phân trên mỗi danh sách minA[i] để tính.
Cho e hỏi, không biết cách làm của e đúng không: e cũng chặt nhị phân giống mấy a.VD độ dài dãy tăng dài nhất là res. E dùng 1 mảng mark[i] để đánh dấu a[i] nằm ở đâu trong độ dài từ 1->res. Rồi sau đó dùng c[i] để đếm ở độ dài i (i=1 -> res) thì có bao nhiêu a[]. Cuối cùng kết quả sẽ là c[1]*c[2]*...c[res].
Mình cũng làm thế được có 61.11 điểm. chẳng hiểu sai chỗ nào.
Mình sai ngay test này:
4
3 4 1 3
Hiểu. đã biết tại sao sai.
Bạn sửa được chưa?
Chưa nữa. Trình mình chưa làm nổi bài này.