Bài này mình làm như sau: Với mỗi (i, j) thì mình xét 4 cạnh kề với nó và tính độ chênh lệch. Tìm độ chênh lệch nào xuất hiện nhiều nhất và dfs với độ chênh lệch đó.
Nó chưa tối ưu và chưa full điểm.
Cho mình hỏi thuật toán bài này là như thế nào ?
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.
Bài này mình dfs+dp f[i][j][k] là đến ii (i,j) và độ chênh lệch là k, rồi lan ra các ô kề nó thôi, nhưng độ chênh lệch có thể rất lớn (tầm 10^6) nên mình hash nó lại cho chỉ còn trong khoảng từ 0->49 thôi
Bài này có thể duyệt tất cả các mức độ cao rồi dùng disjoint set. Một cạnh lưu (x, y, w).
Cảm ơn a. Tội cái e chưa học hash nên ko cài được :D
x và y là gì vậy anh?
w là chênh lệch độ cao ạ?
x, y là đại diện cho 1 đỉnh (u, v). Ánh xạ hết cái bảng n*n thành mảng 1 chiều thôi
master hướng dẫn kĩ hơn đc ko ạ :sexy:
Đầu tiên bạn chuyển hết bảng n * n về mảng 1 chiều.
Thì nhận thấy là a(i, j) <= 10^6 nên độ chênh lệch D <= 10^6. Từ đó tạo một cái vector[D] lưu tập các cặp đỉnh (u, v) có độ chênh lệch là D.
Sau đó duyệt từng độ chênh lệch D, với mỗi D xét tất cả các cặp (u, v) có độ chênh lệch D, dùng disjoint set tìm cái liên thông max.
Em làm như anh nói rồi ạ. Được 90đ là bị TLE hay WA vậy anh?