VOLIS - Dãy con không giảm dài nhất
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 1 dãy số nguyên a[1], a[2], …, 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]], ..., a[x[k]] (k là một số nguyên) sao cho 1 ≤ x[1] < x[2] < ... < x[k] ≤ 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], …, 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 ≤ 1000.
- 0 ≤ D ≤ 10^9.
- 0 ≤ a[i] ≤ 10^9.
- Trong 30% số test, D = 0.
Example
Input:4 1 6 4 3 2 Output:
3
Giải thích: Có thể biến đổi dãy thành 6 3 3 3.
- Người up: voj
- Nguồn bài: Nguyễn Vương Linh