Editorial for HEIGHT

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Nguồn: Free Contest

Với học sinh thứ $i$ ~i~, đầu tiên ta đi tìm số học sinh có cùng chiều cao $h_i$ ~h_i~ và đứng ở vị trí bên trái $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(i)~ là học sinh gần nhất ở bên trái học sinh $i$ ~i~ có chiều cao lớn hơn hoặc bằng $h_i$ ~h_i~. Ta có thể dễ dàng tính được mảng $L$ ~L~ sử dụng stack.

Đặt $dp(i)$ ~dp(i)~ là số học sinh bên trái học sinh $i$ ~i~, có chiều cao bằng $h_i$ ~h_i~ và học sinh $i$ ~i~ có thể nhìn thấy được. Công thức quy hoạch động là:

$dp(i) = dp(L(i)) + 1$ ~dp(i) = dp(L(i)) + 1~ nếu $h_i = h_{L(i)}$ ~h_i = h_{L(i)}~.
$dp(i) = 0$ ~dp(i) = 0~ nếu $h_i < h_{L(i)}$ ~h_i < h_{L(i)}~.

Độ phức tạp: $O(n)$ ~O(n)~.

Editorial for HEIGHT

Comments