VO 12 Bài 4 - Dãy con không giảm dài nhất
View as PDF
Submit solution
Points:
0.43 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho ~1~ dãy số nguyên ~a[1], a[2], \dots, a[N]~. Bạn có thể cộng hoặc trừ mỗi phần tử đi một lượng tối đa là ~D~ (dãy số sau khi cộng/trừ có thể xuất hiện số âm hoặc số thực). Hãy tìm độ dài của dây con không giảm dài nhất của dãy số, nếu cộng/trừ các phân tử một cách tối ưu.
Lưu ý: dãy con của dãy số là dãy số ~a[x_1], a[x_2], \dots, a[x_k]~ (~k~ là một số nguyên) sao cho ~1 \leq x_1 < x_2 < \dots < x_k \leq N~.
Input
- Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~D~.
- Dòng thứ ~2~ chứa ~N~ số nguyên ~a[1], a[2], \dots, a[N]~, các số được cách nhau bởi ít nhất ~1~ dấu cách.
Output
- Một dòng duy nhất là độ dài dãy con không giảm dài nhất trong phương án tối ưu.
Giới hạn
- ~0 < N \leq 1000~.
- ~0 \leq D \leq 10^{9}~.
- ~0 \leq a[i] \leq 10^{9}~.
- Trong ~30\%~ số test, ~D = 0~.
Sample Input
4 1
6 4 3 2
Sample Output
3
Note
Giải thích: Có thể biến đổi dãy thành ~6 3 3 3~.
Comments