Thi thử Tuyển sinh Lớp 10 Chuyên Tin Hải Phòng năm 2026

Nov 14, 2026, 19:00 – 18:59 (02:30:00) Live
Time Remaining 364 days 21:50:28
My Score
0 / 500
Rank
- / 2

D. Bài 4. Tấm gỗ

100 points 1.0 s 256 MB binary-search dp

Tại một xưởng chế biến gỗ, người ta có $N$ tấm gỗ được xếp thành một hàng theo thứ tự từ $1$ đến $N$. Sau khi gia công, mỗi tấm gỗ có một chiều cao xác định, không nhất thiết bằng nhau. Để đảm bảo tính thẩm mỹ, người thợ muốn giữ lại một số tấm gỗ sao cho khi nhìn từ đầu hàng đến cuối hàng, chiều cao các tấm gỗ còn lại thỏa mãn một trong hai dạng sau:

  • Tăng nghiêm ngặt: mỗi tấm đứng sau có chiều cao lớn hơn tấm đứng trước;
  • Giảm nghiêm ngặt: mỗi tấm đứng sau có chiều cao nhỏ hơn tấm đứng trước.

Người thợ được phép loại bỏ tùy ý một số tấm gỗ khỏi hàng.

Yêu cầu

Hãy xác định số lượng tấm gỗ ít nhất cần loại bỏ để dãy còn lại thỏa mãn một trong hai điều kiện trên.

Dữ liệu vào
  • Dòng 1: Chứa số nguyên dương $N$ ($1 \le N \le 10^5$);
  • Dòng 2: Chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$), trong đó $a_i$ là chiều cao của tấm gỗ thứ $i$.
Dữ liệu ra
  • Ghi ra một số nguyên duy nhất là số tấm gỗ cần loại bỏ ít nhất.
Giới hạn & Subtasks
  • Subtask 1 (40% số điểm): $N \le 25$;
  • Subtask 2 (30% số điểm): $N \le 2000$;
  • Subtask 3 (30% số điểm): $N \le 10^5$.
  • Thời gian chạy tối đa: 1.0 giây.
  • Giới hạn bộ nhớ: 256 MB.
Sample Input 1
5
1 4 2 3 9
Sample Output 1
1

Giải thích: Giữ lại các tấm gỗ có chiều cao $1, 2, 3, 9$ còn bỏ đi tấm có chiều cao là $4$.

Sample Input 2
7
8 1 7 3 5 2 1
Sample Output 2
2

Giải thích: Giữ lại các tấm gỗ có chiều cao $8, 7, 5, 2, 1$ còn bỏ đi tấm có chiều cao là $1, 3$. Hoặc giữ lại $8, 7, 3, 2, 1$ bỏ đi $1, 5$.

Sample Test 1
AC 3 ms 1.2 MB
Sample Test 2
AC 2 ms 1.1 MB
Sample Test 3
AC 3 ms 1.3 MB