Dãy con tăng

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Bài toán dãy con tăng dần là một trong những bài toán quy hoạch động được ứng dụng nhiều trong các bài toán tối ưu. Dãy con tăng của dãy a1, a2, …, an là dãy 1p1 < p2 < … < pk trong đó k là số lớn nhất sao cho ap1 < ap2 < ⋯ < apk.

Đức là một học sinh thông minh, thích tìm tòi và khám phá những điều mới lạ nên bạn ấy đã biến đổi nôi dung bài toán như sau:

trước tiên Đức chọn một đoạn liên tiếp trong dãy a1, a2, …, an và một số nguyên d (-xdx). Đức thực hiện tăng giá trị các phần tử trong đoạn đó lên d (d có thể bằng 0) và bạn ấy muốn biết là sau phép biến đổi này độ dài dãy con tăng dài nhất là bao nhiêu.

Em hãy viết chương trình giúp Đức nhé!

Dữ liệu vào có cấu trúc sau:

  • Dòng 1 ghi hai số nx (0x109).
  • Dòng 2 ghi dãy a1, a2, …, an ( 1ai109).

Kết quả ghi ra một số nguyên duy nhất là độ dài dãy con lớn nhất tìm được.

Ví dụ:
INPUT
Copy
8 10
7 3 5 12 2 7 3 4
OUTPUT
Copy
5

Ràng buộc:

  • 30% test tương ứng với 30% số điểm có n1000.
  • 30% test tương ứng với 30% số điểm có n200000x=0.
  • 40% test tương ứng với 40% số điểm có n200000.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.