Tóm tắt đề bài

Cho ~n~ hình chữ nhật, mỗi hình có chiều dài là ~d_i~ và chiều rộng là ~r_i~.

Hình chữ nhật ~A~ được định nghĩa là lớn hơn hình chữ nhật ~B~ khi:

• Hoặc diện tích hình chữ nhật ~A~ lớn hơn.
• Hoặc nếu diện tích bằng nhau, chiều dài hình chữ nhật ~A~ lớn hơn chiều dài hình chữ nhật ~B~.

Hãy tìm độ dài của dãy giảm dài nhất (không cần liên tiếp) của các hình chữ nhật.

Subtask 1. ~n \le 10^3~

Gọi ~dp[i]~ là dãy hình chữ nhật giảm dài nhất, khi xét tới hình chữ nhật thứ ~i~ và ta có chọn hình chữ nhật thứ ~i~.

Ta có công thức truy hồi:

• ~dp[i] = 1~ (cơ sở, dãy một hình chữ nhật luôn thỏa mãn).
• ~dp[i] = max (dp[i], dp[j] + 1)~ nếu thỏa mãn một trong các điều sau:
  • ~area[j] > area[i]~ với ~area[x]~ là diện tích hình chữ nhật thứ ~x~.
  • ~d[j] > d[i]~.

Kết quả sẽ là ~max~ của mảng ~dp~.

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

Subtask 2. ~n \le 10^5~.

Ta sẽ đánh chỉ số các hình chữ nhật theo cách thỏa mãn: gọi ~a[i]~ là chỉ số của hình chữ nhật thứ ~i~, nếu hình chữ nhật thứ ~i~ lớn hơn hình chữ nhật thứ ~j~, thì ~a[i] < a[j]~.

Nếu đánh số được theo cách này, bài toán sẽ là bài Dãy con tăng dài nhất.

Ta sẽ sắp xếp lại các hình chữ nhật theo đề bài. Sau đó, chỉ số của hình chữ nhật thứ ~i~ sẽ chính là vị trí của hình chữ nhật đó trong dãy đã sắp xếp. Cần cẩn thận tránh trường hợp có hai hình chữ nhật bằng nhau.

Độ phức tạp: ~O~ (~n \times log~ ~n~).