https://www.mediafire.com/folder/7a38eesdp47d2/DauNgoac
Em đang tắc bài này ạ: 1 dãy dấu ngoặc hợp lệ là 1 dãy ký tự "(" và ")" định nghĩa như sau:
1) Dãy rỗng là 1 dãy dấu ngoặc hợp lệ độ sâu 0
2) Nếu A là dãy ngoặc hợp lệ độ sâu k thì (A) là dãy ngoặc hợp lệ độ sâu k +1
3) Nếu A,B là 2 dãy hợp lệ với độ sâu lần lượt là p,q thì AB hợp lệ độ sâu max(p,q)
Độ dài của dãy là tổng số "(" và ")"
VD: Các dãy có độ dài 8 và độ dài 3:
((()())) ; ((())()) ; ((()))() ; ()((()))
Yêu cầu: Tìm các dãy có độ dài n (n chẵn), độ sâu k (làm được với n càng lớn càng tốt)
Vấn đề ở đây là em chỉ làm được đến n=20 thôi ạ, từđấy trở đi máy chạy rất chậm (n=23, mất 13s, n=30 mất >20phút ). Mọi người giúp em làm sao để khi n lớn máy vẫn chạy ngon với ạ
Ý tưởng của em là: Đặt open, close là số ngoặc mở và đóng đã dùng, depth là độ sâu hiện tại, left là tổng số ngoặc còn lại,max là độ sâu lớn nhất đã đạt được. Em loại trường hợp bằng cách này ạ: Tại str[i] (vị trí đang xét)
1) open=n/2 => Chọn ")"
2) open<=close => Chọn "("
3) open-close=left => Chọn ")"
4) str[i-1]=")" và depth=1 => Chọn "("
5) Nếu không được thì chọn từng TH
Trong đó, với ")", nếu (max<k) và (n/2-open)<(k-depth+1) thì sẽ loại trường hợp ")" (Đoạn này cũng kỳ ạ, dù em có cho vào hay không thì vẫn ra kết quả đúng nhưng mà với n lớn, em thử bấm giờ thì thấy cả 2 cách không khác biệt mấy ề thời gian ạ ).