Xóa Ít Phần Tử Nhất Để Dãy Tăng
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy số nguyên $A$ gồm $N$ phần tử. Bạn cần xóa đi ít phần tử nhất sao cho các phần tử còn lại (giữ nguyên thứ tự ban đầu) tạo thành một dãy tăng nghiêm ngặt.
Dữ liệu vào
- Dòng đầu: số nguyên dương $N$ $(1 \le N \le 10^5)$.
- Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^9)$.
Dữ liệu ra
- In ra số lượng phần tử tối thiểu cần xóa.
Ví dụ
| Input | Output |
|---|---|
| 6\n5 1 2 6 3 4 | 2 |
| 5\n1 2 3 4 5 | 0 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion