Xóa Ít Phần Tử Nhất Để Dãy Tăng

Binary-search Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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
Draft saved