Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.
Với học sinh thứ ~i~, đầu tiên ta đi tìm số học sinh có cùng chiều cao ~h_i~ và đứng ở vị trí bên trái ~i~. Việc tìm số học sinh ở bên phải có thể xử lí tương tự.
Đặt ~L(i)~ là học sinh gần nhất ở bên trái học sinh ~i~ có chiều cao lớn hơn hoặc bằng ~h_i~. Ta có thể dễ dàng tính được mảng ~L~ sử dụng stack.
Đặt ~dp(i)~ là số học sinh bên trái học sinh ~i~, có chiều cao bằng ~h_i~ và học sinh ~i~ có thể nhìn thấy được. Công thức quy hoạch động là:
~dp(i) = dp(L(i)) + 1~ nếu ~h_i = h_{L(i)}~.
~dp(i) = 0~ nếu ~h_i < h_{L(i)}~.
Độ phức tạp: ~O(n)~.
Bình luận
Bạn cần đăng nhập để viết bình luận, trả lời và bình chọn.
nếu
.
nếu
.
Bình luận