Em có một bài này và muốn làm theo QHD
Em có công thức quy hồi như này
Tuy nhiên chỉ pass 1,2 test . Mọi người có thể cho biết e sai ở đâu không.
Ma trận con đối xứng
Em có công thức quy hồi như này
Tuy nhiên chỉ pass 1,2 test . Mọi người có thể cho biết e sai ở đâu không.
Điều kiện bị thiếu rồi bạn.
2 Likes
Giả sử bạn có ma trận con 2x2 đối xứng như sau:
A X
X B
giờ bạn muốn mở rộng ra thành 3x3 thì bạn phải kiểm tra 2 điều kiện chứ không phải 1.
Ma trận 3x3 sẽ ntn:
A X Y
X B Z
Y Z C
Nói chung bạn mở ra (m+1)x(m+1) thì bạn phải kiểm tra m điều kiện mới chính xác. Tức là bài này cấp O(n^3) hay O(kq*n^2).
Với lại b[n][n] cũng không phải là nghiệm vì ma trận lớn nhất có thể không tới ô đó được. Bạn phải scan lại sau đó.
2 Likes
Đoạn trên mình hiểu rồi. Còn phần độ khó mình không biết tính 
áng chừng được mấy bài dễ thôi. Để mình thử làm lại 
Bài này có thể cải tiến thành O(n^2*logn) nếu sử dụng hash
1 Like
Làm như thế nào vậy bạn?
1 Like
phần quy hoạch động thì công thức vẫn không thay đổi, tuy nhiên phần kiểm tra điều kiện mình sẽ tính trước mb[i][j] là độ dài dài nhất của dòng i, cột j
def max_bound(a,i,j):
for k in range(1,min(i,j)+1):
if a[i][j-k]!=a[i-k][j]:
return k
return min(i,j)
cách này có dpt là O(n)
để giảm thời gian của hàm này, sử dụng rolling_hash theo dòng, cột theo chiều ngược lại, sau đó sử dụng tìm kiếm nhị phân để tìm đoạn dài nhất.
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?